There is no Tivo based HD DVR from DirecTV anymore. You'll only find one used. And it won't get any new HD channels and eventually any HD channels as they will all be MPEG4 which the HR10 cannot get.
As for channel changing, have you ever had a DVR before? It's just a nature of the beast that it's slower. Plus they are made to record, not channel surf. My DirecTivo's take about 2-3 seconds or so to change channels. It has to dump the buffer and start recording the new channel. This takes some time. Now on the HR20 add in HD decoding and then the MPEG4 decoding it will add more time.
Turn Native to OFF and just leave it at the native resolution of your TV. This will have the fastest channel changes. 3-5 seconds is my normal, closer to 5 when going from SD to MPEG4 HD. Totally normal. I then manually change format to 480i if I'm watching an SD show that would look better by letting my TV do the upconversion and stretching.
If you have Native ON not only will you have the 3-5 seconds of the HR20 you'll get an added delay as it "searches" for the correct resolution if you have more then 2 chosen. AND you'll also get a delay from your HDTV iteself as it has to resync itself to the resolution chosen. So you might end up with 7-8 seconds depending on the speed of your TV to sync up.
Personally I have a 1080i TV. I have chosen the formats of 480i and 1080i on the HR20 and turned Native to OFF. I leave it at 1080i piller box which will display HD normally and SD in 4x3 with piller boxes on the side. Looks great, channel changes are not bad (but then again I rarely watch live TV). If the SD show is letterboxed I manually switch the format to 480i and let my TV do it's magic.
This took me about 2-3 weeks of playing around with various settings to get the right combination that worked for me. You will probably do the same. There is no right answer for native on or off or what formats to choose, you'll have to figure out what works best in your setup.