Go for a shoe with good cushioning. I have a pair of Asics racers I use for, well racing, and for fast, short runs but they f#ck my knees if I do anything too long. As do my trail shoes (Salomons) if worn on the road.
When it comes to insoles, get a podiatrist to check you out so that they are done properly.
My girlfriend wears Nike Frees and says they're great. They scare the shit out of me because they look like carpet slippers.
But, as Josh says, go with your feeling. Bodyweight, force of footstrike etc. all varies. Just don't run in Chuck Taylors (always known as Converse All Stars in the UK).
Incidentally my best friend was very, very fast at school and out on the track could beat people in spikes while wearing CTs.