More random thoughts: shopping list
I assume you're going to want to do some hiking in places like Arches and other Southwest parks. A few things to include in your "Walmart list":
Duct tape for emergency tent and air mattress repairs.
Day pack for hiking.
Several water botttles.
Moleskin (and scissors) and elastic bandages ("Band aids") for blisters.
Sunscreen.
Flashlights (plus a headlamp or two from somebody like Petzl; great for reading in bed and when you need your hands free in the dark).
Spare batteries for all the above.
As for water. It can get really hot on the trail (especially in the Southwest parks). You're going to want and NEED water. I probably need more water than most people, but I usually carry 3 liters (quarts) of water (in 3, 1-liter bottles) if I'm going to be hiking all day. I carry two in my pack and one hanging from my belt on a carabiner so it's handy for taking a quick drink (water you don't drink isn't doing you any good).
On one hike, 3 liters wasn't enough. My wife and I hiked 4-6 miles in Supai canyon on a hot day. Thankfully close to the turnaround we ran into one of the tribe members selling Gatorade for $5 a bottle out of a cooler. Best $10 I ever spent, as our water was about gone and we were only halfway done.
As for footwear; unless you're going off-trail decent athletic shoes will be fine.
Hiking in a National Park is the best way to really experience the park, I highly suggest (depending on your time and fitness level) that you try to do as much as possible.
One more thing: since we're talking hiking options; check out this thread.