Lydia DOES level with you. You can check her level with console command and she is always the same level as i am.
Really? Several sources say otherwise. Not saying I don't believe you, I just can't check as I'm on a PS3. I would prefer that were true, but she got weaker and weaker for me (yes, I kept her in upgraded armor). And when I got Jardis she kicked butt.
EDIT: I wonder if "stats" and "level" are two separate things in this situation. Maybe her level reflects yours, but her actual stats never change? Here's the quote from uesp.net:
A follower's stats are determined based on the level the player is at when he or she first enters the zone that the follower is in. Once generated, the follower's stats do not increase at all. For example, Lydia is usually one of the first followers players will have access to, and most players receive her at a lower level. As such, most players' Lydias will have low stats for the entire game.