Hi,
I have used PDAs with Memory Map for about five years now.
It works very well and is excellent for navigation etc.
Older PDAs will require a bluetooth GPS receiver which do work well but can be a pfaff.
The newer models have built in GPS which is easier.
The main issues are battery life and durability (there isn’t any).
I would recommend the O2 Orbit or MDA Compact III (same phone more or less) as they have good battery life for a PDA (about 7 hours on a low backlight setting, more if you turn the backlight off).
I currently use a MDA Compact IV which is very small but the battery life is pants. I bought an extended battery (double the life) and can get about 5.5 hours of GPS use with a high backlight on. I reckon it will get near the 7 hours with the backlight off if not more.
A good waterproof case is the Boxit range. I have used them since I started with PDAs and they have never been damaged by water or crashes.
I would also recommend RunGPS which is a bike/run specific program for GPS. Has maps and all sorts of training/racing stuff incluging heart rate.
Regards