If you want to form two 'Uber-blocs' of geo-political power - then go straight to the Emperor of Kusari and forge a direct alliance.
You will then have Rhineland/Kusari squared off against Liberty/Bretonia (who I might add already have a head start with their Treaty of Curacao).
Remember though, this would turn individual House wars into one single bloody mess to make the Hispanic wars look like a schoolyard tiff in comparison - and would even eclipse the Nomad War with all four Houses squared off!
If you dont want to up the stakes in this way, then go with your direct neighbours the GMG. They are keen to put the past behind and gain a foothold in another House commercial market - Rhineland is doubtless keen to secure a fuel supply for the war effort.