Man, these answers are confused. Which is understandable, because this is complex, but quoting Wikipedia isn't going to do it. Here's my understanding, based on holding a diplomatic passport for 18 years and seeing all this first hand & up close.
So on a purely practical level, Doc's got it right: embassies and consulates are pretty much interchangeable from a traveller's view, as they both provide consular services like visas. All things being equal, it's usually better to deal with an embassy since they're usually larger and better resourced, and on occasion handle things that consulates don't.
On a legal level, let me try to straighten out the terminology a bit.
- An ambassador is a direct representative of a head of state to another country, which is why each country only has one.
- A consul is a representative of a government to another, and there can be many of these per country.
- An embassy is a permanent diplomatic mission (read: a delegation of diplomats) led by an ambassador. The term is often also used for the physical building they occupy, but that's more correctly termed a chancery.
- A consulate is a government delegation led by a consul. Likewise, the word is often used to describe the building itself.
- Consular services is the umbrella term for services provided to individuals: visas, passports, etc.
- A honorary consul is a local eminent person, often a citizen of the host country with business ties to the other, who has been granted (very) limited powers to provide consular services in a place that wouldn't otherwise have any.
- An honorary consulate is wherever said eminent person chooses to hang his or her fancy plaque on the wall.
In theory, the Vienna conventions try to divide the roles of diplomats and consuls, so that diplomats/embassies take care of state-to-state relations and consuls/consulates should handle the day-to-day grunt work of providing consular services. In practice, though, these roles are happily muddled; while consulates don't do state-to-state diplomacy, virtually all embassies handle consular services. Sometimes the embassy has a separate "consular division", which may even be in a different location, but it's still overseen by the ambassador and thus an integral part of the embassy.
Finally, having a full-fledged consulate without a corresponding embassy would be unusual in the extreme. What's more common is that an ambassador is accredited to multiple countries, and the "sub"-countries without an embassy have honorary consulates.