Your asking a lot of questions there bcaslis
In my humble opinion, and that of many forum regulars here, the TivoHD is about, oh, infinity times better than the FiOS DVR. The only real issue you might potentially have is the "pixellation" issue, which you can mitigate with attenuators like I do.
When the channel listing gets changed and upgraded in July, Tivo should handle it all without intervention. It will remap your scheduled recordings to their new channels, and probably send you a message about your lineup being changed. Nothing to worry about there.
Image quality, partcularly on HD channels, is excellent compared to Comcast, and Tivo will have no affect on that.