日本人が多いと言われるのは15区、16区、ヌイイー、ブーローニュ辺りでしょうか。
パリ市内でも92県でも、エリアによって家賃に差がありますし、条件(広さ、セキュリティ、エレベーターや駐車場)でも変わってきます。最近は空き部屋が減ってきて探すのが大変な上に家賃も上がってきています。ご夫婦でお住まいだと、日本人学校のバス停のしばりはなくても、パリ郊外への通勤の便の良いところという制限がありますよね。
いまの情報ではちょっと漠然としていて回答がつきにくそうです。探すエリアをある程度絞れたら具体的な回答が得られるかもしれません。
出向先の方に聞けないのでしたら、日系不動産に問い合わせてみてはいかがでしょう。

参考になった

そのページ、出ませんね……
そこで提携機関（保険会社）のサイトなどから「GRLパスポート取得」にアクセスしてみましたが、毎度、
もうそのページはないと表示されます。
この四月にまた法律が変わるとか、どこかに書いてありましたが、そのせいでサイトは変更中かも……。
でもGRLのサイトに問い合わせの電話番号が入っているし、検索すると
パリの提携機関の住所もわかりますので（左側の帯の部分）
そちらに照会・手続きをなさるといいのでは。
不動産会社にお聞きになるのもいいかと思います。
GRLの保険料は大家さん払いですね。いい大家さんですね。

参考になった

保証人の代わりになるのは、まずLOCA-PASS。家賃滞納の際の保証になるシステムです。
詳しくはこちらを。フランス語ですが……
http://vosdroits.service-public.fr/F18493.xhtml
http://www.aidologement.com/1-logement/locapass-caution-la-garantie-locative.asp

それから、銀行保証 (Caution bancaire) もあります。口座のある支店で手続きをしますが、一般的には、家賃１年分がブロックされますので、潤沢な資金がないといけません。
http://vosdroits.service-public.fr/F16124.xhtml

参考までにこちらも：
http://bbs.arukikata.co.jp/bbs/tree.php/id/362121/-/parent_contribution_id/362121/

一定期間の家賃をまとめて前払い、というのもいいかもしれません。

上記の代替策を提案するなら、大家さんとの話し合いが必要ですね。

参考になった