If you're wearing tennis shoes for squats, you're doing it wrong. There's one trait that your shoes must have: a hard sole. Squishy soles are the enemy, so tennis shoes, running shoes, and cross trainers are out.
To heel, or not to heel? That is the question. A flat soled shoe will encourage a lifter to recruit the posterior chain by sitting back into the squat. The tried and true choice for a flat soled squat shoe is the Converse All Star. Wrestling shoes are perfect, as well.
A heeled squat shoe will shift the emphasis to the quads, allow the lifter to stay more upright, and make it easier to get to depth. The cool thing to do is to buy olympic lifting shoes with wooden heels. For the more frugal, like myself, men's dress shoes accomplish the same thing. Just be careful to get a pair with a solid, non-padded sole, or just rip the insoles out completely. One can also spring for dedicated powerlifting squat boots, but they're ungodly expensive.
When it comes to the bench press, it doesn't make a big difference, in my opinion. However, a solid heel is still desirable. A heeled shoe can make it possible to push the feet back farther, making it somewhat easier to arch.
For the deadlift, there's not much question. A flat shoe with a thin, hard sole is ideal. Thinner soles mean less range of motion. For that reason, many lifters actually wear what's called deadlift slippers. I've also seen women wear ballet slippers. Personally, I wear Converse All Stars with the insoles ripped out, leaving only a thin rubber sole between my foot and the platform.