Even with used sets, DVI inputs are rare and I don't think I've ever come across a DVI to HDMI cable that has a female end. Regardless, yes, both ends should be male.
It really boils down to what resolution your HDTV is going to be (1080p, 1080i/720p, or 720p) and how long of a cable you need. While your graphics card may support DVI-D Dual Link, it may not be necessary to utilize a DVI-D Dual Link cable (good idea for longer runs and higher resolutions). For the record, I'm using a 35' DVI-D Single link to HDMI cable to connect this PC's 8800GTS-640 (DVI-D Dual Link ready) to my 1080p projector. Works without a hitch.
Edit: Depending on your needs, anything on this page
should suit your needs.