best opening to pair with the nimzo

QID, you can go for similar positions in both openings (Nimzo and QID) if you'd like

Such as this:

Queen's Indian Defense: 1 d4 Nf6 2 c4 e6 3 Nf3 b6

QID and QID ideas straight up fail against the 3. g3 move order, and it's not worth learning 3 full openings as Black against the d4 c4 complex. Personally, I have found the BID to be worth playing, as the Bogo has similar flexibility, solidity, and style to the Nimzo.

Perhaps it's merely the variation of the BID you're disliking.
Black has five options in the 3. g3 Bb4+ 4. Bd2 variation: 4... Be7, 4... Qe7, 4... a5, 4... Bxd2+, and 4... c5.
Black has the same five options in the 3. Nf3 Bb4+ 4. Bd2 variations, but in a different order of relative strength: 4... Qe7, 4... a5, 4... c5, 4... Bxd2+, and 4... Be7.
Against 4. Nbd2, Black has six options: 4... b6, 4... 0-0, 4... d5, 4... c5, 4... d6, and 4... a5.
Against 4. Nd2 (in the 3. g3 more order), Black has 3: 4... d5, 4... c5, and 4... 0-0.

That's a lot of options, and the nice thing about the BID is that it's relatively low-theory, so it's feasible to play more than one of these variations, especially in shorter time controls.

If you decide still that the BID is not for you, the Benoni is best against 3. g3 if you like the QID or Blumenfeld against 3. Nf3, but that is still 3 full openings against the d4 c4 complex, so it might be worth investing time into the 3. Nf3 Benoni, which is better for White than the 3. g3 variations. The Open Catalan is of course ultra-solid against any and all White move orders and is quite an interesting gambit to accept with many ways to play as Black, I'd highly recommend looking into this if you like cutting-edge theory and a mix of classical and engine ideas.

Going for a QGD/Ragozin/Vienna/Semi-Slav is fine and well, but you must have answers to 3. g3 d5 4. Bg2 or 4. g3, and my proposal is a Rapport special: 5 ...Ne4! intending a pseudo-Stonewall structure. The move order isn't important up to move 5, 3. g3 d5 4. Bg2 Be7 5. Nf3 Ne4! or any combination of those moves as White has no reason to expect Black will drastically shift the structure, tone, and style of the game in such a unique way rather than opting for the safer, stronger, and more familiar Catalan. Against every sane sixth move, 6... f5 is a strong response, and only against 6. Nc3 would I suggest an alternative 6... Nxc3, as that feels far more natural. Most likely is 6. 0-0 f5. Black is hoping here to delay both a c-pawn move and castling, as the structure of the game is not yet set, and so where Black's king's and c-pawn's ideal squares are is not yet clear. The likely 7. Nc3 clears this up quickly, as suddenly 7... c6 and castling asap is the strongest answer. Against a waiting 7. Qc2, respond with an equally waiting 7... Nd7, then play 8... 0-0 and play from there. Against the aggressive 7. Ne5, lines tend to be weird and there are no reference games, and so I recommend independent study should you choose to pursue this system. There's some very, very fun chess to be played in this mostly-undiscovered system, and I'd recommend at least testing it out in some shorter time controls to see if you like it.

All that being said, my final recommendation is much simpler: learn the pertinent Tarrasch lines. Against 3. Nf3 d5 4. Nc3, the Semi-Tarrasch with 4... c5 is solid. Against 3. g3 d5 4. Bg2 Be7 5. Nf3 0-0 6. 0-0 or any variation thereof, 6... c5 is perfectly sound and the continuation 7. cxd5 exd5 8. Nc3 Nc6 is a direct transposition to the Classical Tarrasch, with the sideline 7. dxc5 Bxc5 8. Nc3 Nc6 9. cxd5 exd5 also being a transposition to various Tarrasch lines. Only the line 7. dxc5 Bxc5 8. a3?! dxc4 9. Qc2/Qa4 is a sound way to stay out of Tarrasch territory without allowing equality, but those positions have no reference games as White and are very simple to play as Black.

Another option not mentioned is the Modern Benoni, which works against both 3.Nf3 and 3.g3.

1.d4 Nf6 2.c4 e6 3.Nf3 (or 3.g3) c5. Many players that play the Modern Benoni will only play it after 3.Nf3 or 3.g3 and play the Nimzo if 3.Nc3 to avoid the Taimanov Variaton (or Flick Knife Attack).

Nimzo is well known to be the "ideal" opening against 1d4 in the chess com opening forum, but it is actually a lot of work to get a complete repetoire with it, in terms of concrete lines and pawn structures to understand.

In the Bogo 4...BxBd2ch is actually very solid, and no move order issues against 3g3 or 3.Nf3. Very trendy top level about ten years ago, Carlsen winning games with it. Doesn't really meet OP's requirements of complicated though.

Personally against the Bogo couldn't find something really liked against 1.d4 Nf6 2c4 e6 3Nf3 Bb4ch 4Nd2 black can end up giving up the bishop pair for basically nothing, or a big space disadvantage.

The Rapport stonewall is interesting Nc6, and h5-h4 in some lines. Personally find Rapport's chess very weird though. Carlsen in chess24 course on stonewall dutch recommended transposing to it from the closed catalan as the perfect stonewall 1d4 Nf6 2c4 e6 3Nf3 d5 4g3 Bb4ch 5Bd2 Be7 and a later Ne4 and f5, in some particular lines he invented Bf4 g5 Be3 Nd6 then Nf5 too, stonewallish.

The queen's indian probably fits the Nimzo conceptally as well as any opening, the main problem are some of the lines are some of the dullest in chess.

At elite level white causes black as much trouble in the Nimzo lines themselves as any other opening.