I use a Garmin Dakota 20 for this purpose. I decided to get a bicycle GPS after riding from Seattle to Olympia with a huge stack of Google map print outs. I still got lost a few times when I missed turns on unmarked roads or bicycle paths with no names. Because it was raining, the papers started disintegrating as well, but mostly I didn't want to spend a whole lot of time stopping, looking at maps, and wondering if I had missed a turn.

You can get the Bike and Hike bundle with the Dakota 10 for $240 at Amazon right now--it includes with a Garmin US Map and bike mount. The 10 doesn't support ANT+ like the 20 does, so if you want cadence and heart rate it recorded on the same device, it won't work for you. I think it may be missing elevation as well and not support micro SD cards, but 400 MB is a pretty good amount of space.

The US map costs $100 separately if you don't go with the Bike and Hike bundle. It allows you to calculate routes like a car GPS does, but it's not nearly as good as Google maps for bicycle routes as it doesn't really have any bicycle trails, so I mostly only find it useful for when I'm in the car. It also has POI (points of interest) which was convenient on a tour when I wanted to know where the nearest restaurant was. Unfortunately, it doesn't know what times restaurants are open.

I didn't go the smart phone route mostly because I didn't want to pay a monthly fee and the Dakota is both waterproof (up to 1 meter) and fairly durable. I've also heard smart phones run out of charge fairly quickly whereas I've used the Dakota for roughly two days per pair of AA's while on a tour.

You can actually load Google map routes to the Dakota and I frequently do so, as Google's bicycle routing is much better than the car-centric Garmin's routing. After you plot a route, grab the bookmarkable link for it (currently a button at the top right), and paste it to http://www.nearby.org.uk/multi-to-kml.php . This allows you to convert the map to KML format.

Then go to http://www.gpsvisualizer.com/ and upload the KML and choose GPX as the output. You can then load that into BaseCamp (the program Garmin has you use to interact with the Dakota). I've never tried to actually get turn-by-turn notifications to work, but just having a marked path and map to follow has been fine for me.

If you choose not to go with the Bike and Hike bundle and don't want to pony up $100 for a map, note that the base map that comes with the unit is pretty useless. There are great maps for free here: http://www.gpsfiledepot.com/maps/state/all . The downside is that you won't get turn-by-turn routing or POI.

Let me know if you have any questions about my set up.