The cabanas in the CCR get a bad rap here - but they are much more spacious than any of the other showers, and the water part of the shower is actually quite good (it's the "tray" and drain which aren't great). So my first choice in your situation would be to book a CCR cabana with You First.

Another option that no-one has mentioned is that if you go airside, you can try the arrivals lounge cabanas, which have huge baths in them. I've never had to wait for one, and the staff always seem a bit reluctant to let me use them (perhaps because they take more cleaning after)!