As someone spends a fair bit of time outdoors, I understand the importance of maps. So, here are a few sources maps that I find quite useful.
National Geographic
One of the great sources of quality black and white maps is National Geographic’s Xpedition. It provides PDFs of maps in vector format that can pretty much be zoomed into whatever resolution you want (of course, it does not contain much detail). And while it is made with kids and education in mind, it is extremely useful, especially when you are planning on venturing into areas totally unknown to you.
Secondly, also from National Geographic is their MapMachine. I would highly recommend MapMachine over traditional map sources if you are going to unknown places (say, the Arctic circle). Its satellite imagery and resolution is far better than what other sources provide (e.g. Google or Yahoo! maps). For instance, look at the results for a fairly middle-of-nowhere place — Barrow, Alaska — for Google Maps and for NG MapMachine.

National Geographic MapMachine map of Barrow, AK

Google Maps map of Barrow, AK
See the nice little frozen arctic and the frozen polar ice cap to the North? That’s what’s missing from Google Maps. Plenty of such small details go a long way in helping you understand what’s out there. Now, Google Earth is also quite similar.

Google Earth map of Barrow, AK
Now don’t get me wrong - I like Google’s traditional offerings for urban locales, but they aren’t the very best for places that are “out there”, so to speak.
Another excellent source of maps is National Geographic’s Topo, which is quite good. If you are a subscriber to the Adventure magazine, they do give the software away for free every once in a while, with some free trails and maps. You can also find several such maps online, or can buy them off NG. Usually, if you hang out in the right outdoorsy forums, you can find someone willing to give you their map collection for free. These usually tend to be very region specific, though.
University of Texas
For physical geographical maps at a slightly higher level of abstraction, I would strongly recommend University of Texas Libraries’ Perry-Castañeda Library Map Collection. It is quite detailed and extremely useful. They have maps of various regions (oceanic, polar, historic, political etc.) as well as the more traditional maps.
They also have a lot of their maps in PDF formats, which is an extremely big plus. On the other hands, some of the older maps are lacking in resolution, which is rather unfortunate.
USGS
The United States Geological Survey has some of the best maps in the world. You can browse a lot of their maps in their online library, or buy their physical maps at the USGS store.
If you are looking to downloading their maps, I would recommend using the USGS Map Locator and Downloader utility. Just enter the name of the place and you can find the list of maps available. Be warned, though - in some of the more remote places, you will find maps that are quite old (e.g. 50s and 70s).
GIS Tools
How can one talk about maps and GIS without mentioning ArcView? ESRI has some of the best GIS software and maps in the world. While their stuff is mostly for commercial/academic usage, it is totally worth its weight in gold.
But it must be mentioned that unless you are quite serious about what you do and genuinely use a lot of GIS applications and data, this will be an overkill for most people. On the other hand, the ArcGIS Explorer is a free version that you could use for personal purposes.

ArcView Explorer map of Barrow, AK
They also have several other “free” tools that you could use to play around with GIS data.
The other company worth looking at is MapTech. They also have some very good navigational and topographic products - although a lot of them seem geared towards sailors and aviators. Often times, you can see them using materials and data from ESRI and USGS for a lot of what they offer.
Atlases & Books
Of course, I still have some fantastic Atlases with me, mostly by National Geographic or by other companies. Most of these use USGS data in unique ways. Lonely Planet also has some good maps on occasion, but their maps aren’t very good for the serious outdoor enthusiast.
At the end of the day, maps are very personal things — once you are used to a particular style and way of doing things, you tend to prefer maps to be in that style. Having used National Geographic maps for most of my trips and ventures, I rather like them.
On the other hand, let me just say that maps are only as good as the navigator. If your navigation and path-finding skills aren’t particularly great, even the best map in the world cannot help you.
Get a good compass and learn to find your way using a compass and a map — once you have that learnt, the rest will automatically follow.