I would definitely recommend you crank up your difficulty to adept at the very least. I started the game on adept with a 2-handed warrior, and the difficulty felt just right for the first 10 levels or so.. then it got too easy so I turned it up to expert. Things were good and balanced until level 28 or so, when I realized the game was again teetering on the edge of being just a tad too easy, so all the way up to master we went. Funny thing is even master has felt too easy since level 35 or so. I'm contemplating using a difficulty increasing mod.
Granted, I have been smithing and enchanting, but I HAVEN'T exploited the alchemy-smithing-enchanting loop which lets you create godlike weapons and armor - I've simply leveled up my crafting skills the honest old-fashioned way. Smithing is the only crafting skill that's hit 100, enchanting is 80 and alchemy in the 50s. Even so, my daedric greataxe does 260-something damage (I think), + 30 points of fire damage. I think I'd one-shot kill everything in the game if I played on adept now.
Still, a game that's impossibly hard is much, much worse and more frustrating than a game that's just a bit too easy. I'm thinking back to Dragon Age 1.. man, that one was impossible on normal difficulty until the late-game when your characters were leveled up. And that's coming from someone who has played the Baldur's Gate trilogy, Neverwinter Nights etc.
Oh and Odysseusgamer, nope, you don't need to restart if you want to change the difficulty.