Also give Saint's Row 2 a shot. Similar sandbox style game that I honestly enjoyed more than GTA4. Granted, a lot of that was due to the person I was playing co-op with, but I loved playing it solo as well.
GTA4 is about the characters and how they get to certain points in their lives. Saints Row 1 and 2 is more arcade action sandbox. More comedy as well. I prefer the GTA style.
If you have good patience, wait for a game called True Crime. It's a sandbox game like GTA, but it's set in Hong Kong where you play a HK native with Martial Arts abilities. It'll be coming out sometime in the fall, possibly by late September.