If you are members of AAA or the equivalent down there, you could always request maps in advance, or pop in one of their locations and pick up maps and tour books.
If not, a map or Internet printout could certainly be handy, just in case. Most gas stations will sell local maps if you're desperate.

I have some Merrill hiking shoes and really love them. They're a bit more sturdy than sneakers. I've used trail running shoes also, and they're similar...but these Merrill's have just a little more support, and are waterproof. I think there's a discussion on shoes over in the Travel Tools forum somewhere. I picked up mine at Dick's Sporting Goods, and I think there's some in Vegas.

Lastly, I'd definitely pack or pick up some sunglasses. I keep a pair in my car, have a dedicated pair for cycling, and have one other just in case. I wear contacts and my eyes are pretty sensitive to the sun, especially during rising/setting.
If nothing else, when you go to Target to get your water and snacks, a $20 pair of sunglasses should work. Plus a hat and sunblock