DirecTV's PVR isn't too bad. I'd say it's the best of the service provider boxes, but IMO the UI is nothing compared to a Tivo (I don't have any experience with Replay, though).

It's probably a long shot for the place you're moving, but you could check if it has FIOS. I love FIOS. Then you could get the TivoHD.