Affordable GPS with maps?
One option would be to use an iPhone. If you use software such as MapMyRide you can integrate it with ANT+ sensors to measure speed, cadence and even heart rate. These sites also have excellent mapping, training review and history functions.

Pros:


You can use your existing phone rather than needing separate hardware
The online version of mapping software allows you to plan routes and review your history


Cons:


Waterproofing the iPhone will be harder than with dedicated hardware, although I have seen solutions (such as Biologic's case) that claim to do this. 
Battery life will be an issue. You'll need to find a way to keep it charging (using a hub generator as seen here) or have battery extenders (as seen in the millions on ebay).
Maps are downloaded from google maps so you'll need to have a data plan.