Red Deer has a really nice downtown in my opinion, even a bit nicer than Lethbridge's. I did a photo tour of the downtown last year. Perhaps TriWolf could furnish us with some of his beautiful pics?
Did you perhaps just go around the city on the bypass, rather than going down Gaetz Avenue? Because there is really no other way to miss the downtown, if you're looking for it. The part of Red Deer you seem to be describing is Gasoline Alley, which is most obviously not the downtown of a city of 100 000 people
It is a refueling and fast food hub on the outskirts of Red Deer, on the QE2, directly in the middle of the corridor between Calgary and Edmonton
It's a bypass around the city, because the city didn't want an extremely busy highway going right through their historic core.