I'll offer some comments and suggestions. It seems very likely that you lack development of certain skills and stats. Hopefully, this will offer you some ideas. You don't need to change the difficulty setting, either, by the way, although you can, of course.
The leveling system in TES games is not imbalanced, nor is it incorrectly implemented, per se, aside from the choice in TES IV to have everything randomly generated in leveled lists, including enemies, loot, etc, with no specific items to bother exploring to obtain. However, as far as general implementation, it works just fine (i.e., you develop characters based on what you do). As far as enemies leveling with you, it makes sense that your reputation would cause stronger opponents to seek you out for one reason or another. Actually, what doesn't make sense in Oblivion is the overall frequency of encounter. There is simply no way that so many encounters could exist within such a small space as they could not survive on the resources available. The problem with everything being random is that there is no goal to strive for and everything becomes simply a roll of the dice with no influence from the character. That's a different issue than general implementation or leveling mechanic, though.
Like any game or simulation, one must learn the rules of the world. This is like our physical existence, too, isn't it? We try to learn the rules and live as best we can.
Although I define major skills as being skills that required special courses, training, practice sessions, etc to develop, I have also played characters where majors mean most used. However, even in such a case, minors does not mean "ignore and do not use."
I play stealthy characters, but not thieves or assassins, per se. It annoys me greatly that Beth and other companies have equated "stealth" with "thief." Acrobats and similar professions do not have to be thieves, after all, and it would be nice for a company making RPGs to avoid equating the two areas.
Many people equate leveling up with getting stronger, but that isn't really true in a traditional RPG sense. Rather, leveling up is supposed to indicate experience in life. Getting stronger is also relative to what you do, of course.
Stealth characters (or magic characters) do not need strength, nor do they need endurance. You can do the math and see why this is so. There are better, more powerful ways to alter such stats through magic (enchantments, potions, scrolls, spells) than can be done through leveling them when they are not your character's focus.
Between stealth bonuses for attacks and poison effects, stealth characters can easily take out any opponent in one hit even on max difficulty. Or you could use magic with stealth bonuses. Either way works.
Stealth characters should excel in speed and agility, and maxing these stats allows them to win or avoid most any encounter. Boosts can be gained through potions, spells, etc, of course.
Note: I also boost Personality early and start with it fairly high (50) compared to many people. I also boost Luck (most important stat, by the way, especially in early to mid levels). My characters tend to use guards and other factions. Speedy, agile, stealthy characters are not for toe-to-toe knock down, drag out fights. I can't imagine a character of such a personality who would want to get into such a brawl. However, leading an opponent into another area to fight someone else makes sense. Commanding them to do so makes even more sense.