Specifically, where can I find a database of zip codes, their lat/lon centers, and intervening "obstacles" (for example, zip codes that are geographically close but separated by the Chesapeake Bay).
The distance not only depends on the origin and destination, but how you want to get between the two. If you're talking about Chesapeake Bay being an obstacle, then it sounds like you might be interested in driving directions.
The Google Directions API can be used to calculate driving routes (distances and times) between two locations. For example, to see routes between the 59715 and 94108 zip codes, you could make this request: http://maps.google.com/maps/api/directions/json?origin=59715&destination=94108&sensor=false (about 1,040 miles)
If you're talking about obstacles, then you're talking about routing around obstacles - and it's not as simple as working with zip code center location data.