My first flight instructor was at least 6'4". He wasn't heavy though (still young). He could fit in a 150, but he looked kind of like a grasshopper sitting there

.
It sounds like to me Todd may want to look for a 150 Heavy (C-172 for you, Todd). They have plenty of room and enough power to get a couple of good sized guys off the ground. They burn more fuel, though, and cost more (my guess is probably $30 to $35 thousand for a nice one).