Scott, the GPS that helped us get back that day is the Lowrance GlobalMap 100 everyone has mentioned. I also have the CD with downloadable maps. With all of the accessories (holder, 12v cord, cd), it was well over $300 out the door, but it's a great unit. Units that offer mapping capability are so much more pleasing to use than a plain speed/direction/track GPS. It's well worth the extra $100 to $200 spent, IMO.
To answer your other question, yes, I downloaded an area map of the Truman region before making the trip to MO...that's why we could see ourselves zipping along (at 68mph) in the detailed topology and named locations shown on the unit.
By the way: My hope is to some day link the GlobalMap 100 with the fishing reports feature you see on the web site, for uploading event data for reports.