Is there a difference between frei and kostenlos?
From what I understand, 'kostenlos' basically means 'free of charge' so you would use that if you were saying 'Mittagessen ist kostenlos' (lunch is free).
The native speaker agrees. ;) "Kosten" are "costs", so "kostenlos" is literally "without cost". Using "frei" when talking about money or "kostenlos" when talking about freedom is completely wrong in most instances (cf. Bellatrix's answer for an exception).
Oh but we do say "Der Eintritt ist frei" (Admission is free) and this is about money but it might be an exception. Generally kangaroopouch is right, "frei" is about freedom or a free space etc. but you can sometimes use it for fees or costs but "kostenlos" is always about money.
As they would say in English, "Free as in beer, or free as in speech?" ....since English uses the same word for both. I'm glad in German they don't, because then you don't even have to ask this question.
So if a person (or airplane bathroom) is "free" in the sense of being not busy or unoccupied, the correct adjective is "frei"?
For the bathroom, yes. You would definitely use "frei".
For a person rather not. I say rather because it would be possible, but really rarely used. But I also can't think of another single word you could use for an unoccupied person. I'm not sure there is one. Probably it is mostly used as in English with describing the state, like "not occupied" or "not busy" (nicht beschäftigt) or you could say "Ich habe nichts zu tun" (I have nothing to do).
"Frei" means you can do something on your will. Ex: free to go, got freedom, etc. "Kostenlos" means "no cost", related only to money. Ex: free càfe, free bread, etc. Hope this hepls.