I currently use a Garmin Oregon 300 GPS Receiver and find it be a terrific device. One of the best features is the ability to load custom maps into the device. There are numerous commercial map products available from Garmin, but there's also a large number of free alternative basemaps available for those that are willing to search the web. (These maps may work for older eTrek/Legend series of receivers, but you may have to experiment a bit.)
The OpenStreetMap.org site offers a "Wikipedia of maps" - anyone can make edits, additions, or deletions to a worldwide map, making the underlying map product very useful (depending on the degree of user interaction, just like on wikipedia). There are a number of free tools that can enable you to convert the OpenStreetMap data to a format recognizable by your GPS receiver but, at least in my experience, these are complicated and confusing to use; besides - a number of people (or services on the web) will do this for you! Most of the free Garmin base maps are based on the OpenStreetMap map data but many have been augmented by their authors to include more details (perhaps from other data sources like trail databases) or improve icon/color selection for GPS receivers.
Most of these maps are "routable", meaning that the BaseCamp software and your GPS unit can follow roads or trails to the destination rather than simply drawing a straight line. In theory, you may also be able to use these maps in car GPS receiver units as well (since I believe Garmin uses the same map format for both devices) to help you in driving around where ever you are going. As of 2011, none of these free maps have elevation data (so that you can plot elevation profiles) as that seems to be a proprietary Garmin data format that no one has reverse engineered yet. If you need to determine elevation profiles for anything, just use BaseCamp to export your route to Google Earth and use its excellent elevation profile tools instead.
For various trips I've done, I've scoured the web looking for good maps for my GPS (after trying and failing to create mine). I found a number of excellent maps for my Garmin (and there are some for other GPS receivers as well) and they're all linked to below.
Note that for the Garmin receivers, there are two "flavors" of map images. One is a large (typically a few hundred MB) .img (such as the standard gmapsup.img) file that you can copy directly on to your GPS receiver and view on the receiver - this is really handy, but doesn't display in Garmin's BaseCamp software unless you have your receiver connected (and even then, it's fairly slow to load since it is being read from the unit itself). The other format places hundreds of smaller map tile img files on your hard drive which cannot be directly transferred to your device by copying. These have to be "installed" onto your machine for BaseCamp to see them, but after that you can use the Garmin MapInstall program (which comes with BaseCamp, but) you may have to dig around in "C:\Program Files\Garmin" to find it) to transfer maps to your GPS unit. The advantage with this method is that you can selectively transfer only the map tiles you need to your GPS unit (rather than an entire country or region, for example) and you can easily view these maps in the BaseCamp software. I recommend the latter approach.
One final note: if you're looking for international maps (and you're not as multi-lingual as you'd like to be) I highly recommend navigating to these links either with Google Chrome or install the Google Toolbar in your browser of choice. These will both allow you to perform instant translation on any page that's not in your native language. Sure, the translations are a bit rough around the edges, but it usually makes it MUCH easier to find the file you are looking for!