I have a 2007 Sonata 4-cyl and I've done quite a bit of reading on Hyundai forums about this. Most people, including me, experience the exact same problem you do. It shows up when you exit the interstate.
There are two main causes:
1 - Crank pulley separating. This is more common on the V6 models, but does happen on the 4 cyl, too. The pulley has a rubber ring that starts coming apart, allowing the outer part of the pulley to stop spinning or spin more slowly than the crankshaft. That causes the power steering to stop working, since the belt isn't turning the pump fast enough.
2 - The belt is slipping for some reason.
I had the exact same problem as you. On mine, it wasn't the crank pulley. I checked it and it was fine.
on mine, there was lots of gunk built up on the pulleys, including the PS pulley. It was down in the grooves of the pulley. I would guess it was oil or the belt itself breaking down. I scraped the gunk off the pulleys, put on a new belt and it fixed the problem. I went with a Bando belt. Made in Japan and fit well.
Replacing the belt isn't too tough, you have to jack up the car and take off the passenger wheel. You remove a small access panel and then you can get at the tensioner. A long-pattern wrench (17mm, if memory serves) makes releasing the tensioner easier. I just doubled-up two wrenches.
