Two basic optimizations
1) Dividing you world into logical chunks. A chunk is a rather large portion of your game world and independent of your actual objects. It is large enough that you can make the simple assumption: You have 2 "collidable" objects, one is in chunk A, the other in chunk B. If A and B do not have a common edge or point, then the said objects cannot possibly collide, so they have a distance of 2 chunks or larger. Then you can disregard them right away. Note that if you use hexagonal chunks, you only have to check for common edges, i.e. you can use a hex-based equivalent to the "Manhattan distance".
2) Distance-based pruning. If the 2 objects in questions are in the same chunk, or in adjacent chunks, you need to refine the check. At the simplest level, imagine a sphere centered around every object that can collide with something else. The sphere is just large enough to completely surround its object, so that neither part of the object can stick out under any circumstances. Then you can conclude that if the distance between 2 objects is larger than the sum of both spheres' radius, then those 2 objects cannot have collided. To optimize this calculation, don't work with distance and sum of radii, but their squares, to avoid calculating expensive square roots.
Only when both checks indicate a possible collision, move on to the more expensive checks, which is probably hit boxes. Remember that the closer your bounding boxes resemble your actual object's geometry, the more expensive things get. You have to find a good compromise between quality and quantity of collision checks, but that depends on your game design entirely.