I have a Garmin eTrex Vista HCX, plus a micro SD card with Open Cycle Map from Open Cycle Map. Not as good as OS Maps, but OK, getting better all the time, and very cheap or free.
You can download the Open Cycle Maps for lots of different countries from the links on the wiki sites on the web (easily googled), but they can only be loaded one at a time on the SD card. I have France and the UK on 2 different cards.
Looks like the newer eTrex 20 and 30 can support more points on the routes (which is an annoyance on the eTrex).
Paul
EDIT: and you can buy bike mounts for it (large diameter rail mounts – about £7)