「夫と２人で」ということなので、お二人とも運転ができる、疲れたら交代できる、という前提で回答します。（私はQueenstown在住です）
普段（アメリカ国内）とは走行車線が逆なので、普段以上に運転が疲れるという想定でご予定を立てられるのが良いと思います。そのために、適宜、運転交代・休憩を織り交ぜることから、google mapの所要時間に+αで旅程を組むのは、とても良いご計画方針だと思います。（お二人が実際にどれくらいかかりそうかは、私には？ですが）
Queenstownからの移動ですが、FranzでもFoxでも、仰る通り、そこまでの大きな違いはないので、どちらでどんな観光・activityをご希望なさるか？どちらに宿を見つけたか？で、どちらの町に宿泊するかを決めればよいと思います。
宿情報ですが、もしまだQueenstownの宿が見つかっていないようでしたら、私が運営するMotel (Bella Vista Queenstown)も検討候補に入れていただければ幸いです。Down town徒歩圏内で駐車場が無料な宿は多くはないです。ぜひ、公式HPをチェックしてみてください。Booking.comなどよりも公式HPのほうが安く予約できます。
残念ながら、FranzやFoxの宿情報に明るくはありませんが、Franzであれば、同じBella Vistaチェーン傘下のモーテルがあります。ぜひ、候補に入れてご検討ください。
「疲れた時にホテル探しすると、以上に時間がかかるし」のくだりが質問内にありますが、現地に着いてから宿を探すのは、掘り出し物を見つけることがある一方で、多くの場合時間の浪費が多いことになりがちです。
3月末ごろからということなので、そこまで逼迫した時期ではありませんが、４月３日からはイースターホリデー、そしてそのまま春休みに続く時期でもあります。私なら、少なくとも、次の町に向かって出発するまでには次の宿を決めて（予約して）から向かいます。
私のやり方は、トリバゴで、あたりをつけて、そこで見つけた候補の公式HPを見つけて確認・予約、なければ電話して予約します。
以上、ご参考になれば幸いです

車椅子のレンタルは、Engage Safetyの他、
薬局（Unichem Remarkables PharmacyやLife Pharmacy Wilkinsons等）でもやっていると聞いています。
街の本当の中心は平坦ですが、少しでも離れると坂道が出現し、離れるに従って勾配のけっこうある坂道が増えます。自走式もご検討なさると良いでしょう。年末ということであれば、日本からのご出発前に、問い合わせ、ご検討なさり、予約しておいた方が良いと思われます。
車椅子でも楽しめる観光スポットですが、クイーンズタウンは、ニュージーランドの中でもバリアフリー化が進んでおり、特に人気スポットは、車椅子でも存分に楽しむことができるところが多いように感じています。ただ、それぞれの場所に辿り着くまでには坂道がある場合が多いので、ご留意ください。人気スポットは単純に湖畔やQueenstown Gardenを散策しても良いですし、町のNo1アトラクションのゴンドラも、車椅子でも楽しめると思います。ゴンドラそばにはKiwi Parkもあります。TSSアーンスロー号でのクルーズも良いのはないでしょうか。ただし、TSSのオプション（対岸のwalter peakで下船して、farm showなどへの参加）については、運営しているreal社に車椅子での参加について問い合わせしたほうが良いでしょう。ワイナリー巡りのツアーも、「車椅子でもどうぞ」というツアー会社はあると思います。郊外の風景・雰囲気も楽しめ良いと思います。
ミルフォードサウンドへのバスと現地でのクルーズがパッケージになったツアーは非常に人気です。まだご予約なさっていない場合に、今から予約できるかは不明ですが、いくつかの会社がやってますので、問い合わせなさると良いでしょう。
私が普段、バスを使っていないので、確証はありませんが、ご同行者の介添えがあればバスの利用自体は問題ないだろうと思います。なお、Beeバスではなく、Orbusと呼ばれています。Beeは、乗車に使うカードの名前です。Orbus公式webのFAQsにwheelchairについてもあるので、探して参考にしてください。空港からについては、バスの利用自体よりも、バス停を降りてから宿泊施設までに急な坂が無いかを危惧します。
以上、ご参考になれば幸いです。

都市間の移動は、レンタカーがお勧めです。それぞれの観光にも大活躍するはずです。宿の選択にあたっては、例えばBella Vistaみたいな、　モーテルタイプの宿泊施設であれば、宿泊施設での駐車代が宿泊料金に含まれていることが通常なので、安心です。町の中心地に立地のホテルでは、駐車場代が別途かかることが多いです。

NZは日本同様に南北に長い島国なので、どこに行くかによって、気候がまったく異なります。私が住むクィーンズタウンの５月は、寒いです。しかし、日本の11～12月頃でも、青森と宮崎ではまったく気候が異なりますよね。それと同じことです。
移動手段はレンタカーが人気です。
治安はおおむね良いです。日本で普段しないようなことをしなければ大丈夫です。（深夜に人気のない場所を女性一人で歩いている。とか。）
地域は好みでしょうから、NZガイドブック（それが人気スポットリストです）をパラパラと見てみて、ご自身が「ここ良さそう！」と惹かれる地域を中心に検討なさるのが良いでしょう。地球儀で見ると小さな国ですが、国土面積は日本の70％くらいある国です。日本から北海道を除いたくらいの地理的広がりでしょうか？たぶん。なので、それを網羅しようとすると異動ばかりに体力と時間を使うことになるので、欲張りすぎないことがポイントではないかと、思います。日本で、本州の全てと九州と四国を、一度の旅行でいっぺんに観光しようとしたら、過酷ですよね。

本格的な、ハイキングとはならないでしょうが、時計を見ながらフッカーバリーのハイキングコースを行けるとこまで行く感じなら可能でしょう。フッカーバリーのハイキングコースは平坦で同じ道を戻るコースなので、自分の現在地までバスの乗降場所からどれくらい時間がかかったかが、そのまま現在地からバスの場所まで戻るための所要時間になります。なので、時間計算を立てやすく、ゴール地点を目指しつつも、時間的に怪しくなった場合はその地点から引き返せば良いだけです。

クィーンズタウン空港から（又は空港に迎えに来てくれて、空港近所の店にて）車をピックアップできるレンタカー会社に、クライストチャーチで返却の予定で予約するのが良いと思います。町中のホテルご滞在の場合は、毎日、駐車料金がかかってしまいますが、車があるのは様々の観光やアクティビティにとっても重宝すると思います。
ただ、クィーンズタウンのご滞在中のご予定・計画にほとんど車が活躍しないとか、バスやタクシー、アクティビティ催行会社の送迎など、代替交通手段で事足りるのあれば、クィーンズタウンの滞在の終盤に、（空港ではなく）街でピックアップ（又は街に送迎に来てくれる）形での予約しておくほうが、総費用としては抑えられると思います。
私の経営するモーテルは、街の中心まで歩いて5分ですが、駐車料金は別途不要ですけどね。
「借りるのは簡単なのでしょうか」のご質問の意図が正直なところ分からないのですが、ネットで予約しておいて、その指示通りに動くだけだと思います。
クィーンズタウン以外のことは、他のロコさんに回答をお任せします。

最短ルートとしては、オークランド空港からクライストチャーチ空港に飛んで、そこからレンタカーでマウントクック村に行くのがおそらく最速コースでしょう。
NZでの全滞在日程が3日程度で、その3日間の滞在場所がオークランドということであれば、そこにマウントクックでの遊覧飛行を組み込むのは現実的ではないように思います。
地理的・距離感的日本に当てはめれば、福岡滞在３日間で、厳冬期に、（当日の天候が悪ければツアーが中止になってしまう）日本アルプスの剣岳での遊覧飛行に参加しようとしている状況です。
これに今回のNZ旅行のすべてを賭けるというのであれば、可能なのかもしれませんが、私はお勧めしません。
ご参考になれば幸いです

「5月と6月ではミルフォードサウンドへ行くにはどちらがおすすめ？」とのご質問、どちらのほうが天候が良いか？という意味ととって答えますと、何らかのデータに当たったわけではなく、私の印象ですが、5月のほうが良いような気がします。
申し上げた天候の安定度は、あくまで私の「印象」でしかありませんが、5月から6月にかけては、晩秋から初冬になる季節です。冬は、タイミング合えば、「青空の下に白く冠雪した山々」という景色に出会える可能性がありますが、その僥倖の可能性に賭けるよりも、少しでも早めの、秋の内のほうが天候条件は良い可能性が大きいように思います。（繰り返しになりますが私の印象です。）
クィーンズタウンからミルフォードサウンドへの空路は、セスナ機になります。予約していても天候が悪いと、そのツアーはキャンセルされてしまいます。日程にご余裕がある場合は、翌日に順延して、また翌日の天候待ちすることになります。
一方、往路はバスで帰路だけ空路の予約をしていた場合は、季節外れの大雪や大嵐などよっぽど酷い天候でない限りはツアーは催行になり、ほぼ間違いなく予約した日にミルフォードサウンドに行くことができます。で、天候が不良の場合は、帰路もバスで帰ってくることになります。もしバスで帰ることになった場合は、若干の返金があるものと思います（たぶん）。
5月にしろ6月にしろ、セスナを安全に運行できない程度に悪い天気になる可能性は、夏に比較すれば高い季節となってきます。
お申し込みを検討なさっているツアーの催行会社に、5月と6月で、フライトのキャンセル率に違いがあるのかを問い合わせるのが良いと思います。
一人旅で運転もできないので無理そうかな？とありますが、もし日本で普段運転しているのであれば、レンタカーでテカポに行くのは問題ないでしょう。
運転ができないけどどうしてもテカポに行きたいということであれば、intercityとかのバスでクィーンズタウンからテカポに一泊二日で行くことは可能でしょう。
又は、great sight 社がマウントクックまで一日行って帰ってくるバスツアーをやっています。「Mount Cook & Queenstown Day Tours」でググればgreat sightのHPは簡単に見つかるでしょう。

もし、ご主人がお一人での運転なのであれば、テアナウ宿泊のテアナウからの運転にするか、クィーンズタウンからバスとのパッケージを申し込まれるのが良いでしょう。道中もバス観光と思えば悪くないですよ。探せば、会社によっては、そのバス車内で日本語解説付きの会社もあったような気もします。
お二人で、運転を交代しながら行けるのであれば、クィーンズタウンからレンタカーでの往復でも大丈夫かと存じます。
遅くなりましたが、ご参考になれば幸いです。

私は、キャンパーバンの経験がないので、そのメリットは正直なところ分かりません。
私はクィーンズタウン在住ですが、クィーンズタウンだと、キャンパーバンは、宿泊できる場所が限定されるイメージです。ホリデーパークかキャンプサイトが選択の中心になりますよね。モーテルも選択肢に入るかもしれませんが、キャンパーバンを停められるかは問い合わせした方が良いでしょう。ちなみに、クィーンズタウンでは街中にキャンパーバン専用のパブリックパーキングが一か所あります。図書館のそばです。でも、宿泊施設のそばに停められないのは不便に感じるのではにかと思います。キャンパーバンのサイズにもよりますが、普通のホテルだとさらに限定されるでしょう。私が働くホテルではダウンタウン内の立地ではありませんが、それでもキャンパーバンの駐車スペースは確保していません。ちなみに、クィーンズタウン近郊エリアでは、キャンプサイト以外、勝手にキャンパーバンで一夜を過ごすというのは、原則禁止されています。
他の地方の状況には正直あまり承知していません。
NZの道路はオーストラリアに比べて、カーブとアップダウンが多いので、大型のキャンパーバンでの運転はより疲れると想像します。借りるなら小型の方が良いでしょう。
通常のレンタカーにしろ、キャンパーバンにしろ、長距離を走行して、広範囲に旅行される場合は、全国展開していて、少なくともクィーンズタウンにも店舗があるレベルのレンタカー会社から借りておくと、困ったときのサポートが受けやすいと思います。
あとは、ネットで値段などの条件を比較して選ばれれば良いのではないでしょうか。特にこの会社がお勧めとかは、ありません。