Fair warning: I've not used a GPS module.
Q3) GPS Units - Any thoughts?
Two of those are 3.3V devices. You will need a "level shifter" (I think that's what they're called).
This one is a bit cheaper and works at 5V...
http://www.parallax.com/Store/Sensors/CompassGPS/tabid/173/CategoryID/48/List/0/SortField/0/Level/a/ProductID/560/Default.aspx