I can't guarantee that this is the correct answer but I've always associated the phrase 'to get cold feet' with someone wanting to go swimming in the sea. It seems a good idea until they step into the water. At this point, they get cold feet and think better of it.
This site repeats the military connection as one possible derivation but also suggests that the phrase may be related to poor people being unable to afford shoes: http://www.word-detective.com/091801.html
(I still like my idea best - even though it's obviously wrong!).
I always thought a person got 'cold feet' at the thought of something scary, simply meant that they had a phenomenon where the soles of their feet went cold and clammy. I have always thought this simply because it happens to me! When I see a person on TV leap off a cliff or something, or I watch the kids on roller coasters, the soles of my feet suddenly go cold.