For immediate replayability, something in the sandbox-RPG genre (Fallout 3, New Vegas, Oblivion, etc.) is always fun as the approach you take can vary each playthrough (though my experience is that there's frequently an optimized approach to the early portions of the game and/or levelling that drains a bit of fun in exchange for the ability to trounce enemies)
If you're looking at long-play type games, you're hard pressed to beat Nippon Ichi's releases, especially in the Disgaea series.
Alternatively, there are short-play games like Prototype and Dead Rising that are just great fun to kill time in.
Ultimately, though, when I think "replay value" I'm actually considering whether or not I'd want to sit though a game again, start to finish at a later date, and I really like a number of JRPGs for that. For instance, to me Chrono Trigger, Suikoden II, Final Fantasy VI, and Lost Odyssey are like favorite books. Sure, you know what's going to happen and it'll take a while to get through, but every now and then it's great to relive it.