2:02 p.m. on July 31, 2007 (EDT)
Gee, one vote for trail running shoes, one for "old clunky boots", and 2 against sandals.
I have to agree with the vote against sandals on 3 counts. First, as Pika said, you have no toe protection with most sandals against stubbing your toe. There are some sandals by the quality manufacturers like Teva that offer some toe protection, but probably not enough.
Second, sandals offer no ankle support. So if you do not have strong ankles, it gets very easy to twist an ankle, especially off trail.
Third, I find that sandals let sand and dirt get under my feet and between my toes, which creates a lot of rubbing, sometimes making large raw areas that really hurt. It's ok for short walks where you have plenty of time to shake the dirt and sand out, but not for a 15 mile hike.
Sandals have some advantages for stream crossings and in the kayak, but a pair of "water socks" actually works better for both. These are light enough and roll up to just throw in the pack for the hike, then use for the kayak part.
As for high top vs trail shoes, I personally use trail runners for a lot of my hiking, including cross country in rough terrain. But I have strong, flexible ankles (from years of cramponing on steep slopes and smearing on steep friction slabs where you need to keep the bottoms of your feet flat to the surface). When I carry really heavy, expedition size loads, I go to higher ankle footgear. If you do not have strong, flexible ankles, you should consider high top boots. These provide some ankle support, but mostly the high top provides a signal to your legs sooner that you have just encountered a rolling rock or are starting to twist your ankle, thus giving more reaction time to your muscles (you get full ankle support only with braces or stiff plastic boots, and in that case, you might get a spiral fracture of the lower leg bones instead of a twisted ankle in a fall).
A way to check your ankle flexibility - while standing, can you roll your feet (bare feet) so the soles are against each other (still standing upright, with all or most of your weight thus on the outside edges of each foot)? Careful! If your ankles are not strong and flexible, you can sprain an ankle or worse doing this. I used to be able to put the soles in complete contact, but at my ancient age, I can no longer get full contact, but I can stand with full weight on the edges.