Yes, you can get true HD from your TiVoHD to your new HDTV. I don't know whether or not you currently have HD service but if you don't you will need to have Comcast upgrade your account to HD. You will not need to change your CableCard and you will be able to tell whether or not you have HD service just by looking at the picture, just make sure the TiVoHD is outputting an HD picture by going into settings and selecting HD output.
I would match the TiVoHD output to the resolution of your HDTV, probably 1080 but could be 720p. If you let us know your HDTV make and model, the resolution will be available online. I have both 1080p and 720p HDTVs in house.
Home Theater - OTA TiVoHD/1.16TB/NSZ-GS8 GTV
MBR - OTA TiVoHD/660GB/NSZ-GT1 GTV
Den - OTA TiVo Premiere/2TB/NSZ-GT1 GTV