I'm in agreement with you and touched on this briefly during my Final Fantasy VIII review. I saw the chemistry between them as early as disc one when Rinoa scolded how cold he came across to his companions and you see them growing even more if you have Rinoa in your party when you go to warn Balamb Garden about the in-coming missile strike, followed by that one scene on Fisherman's Horizon and their kinda, sorta date after his promotion a few scenes later.

I actually did like the space stuff, except for the fact that Rinoa should have been long dead after her life support gave out but that's another discussion.