Just a comment on your National experience -- I have never had any problems with National (it may be because I have not used them in Orlando). I have found them to be courteous and helpful. One thing to consider with them is Emerald Isle -- there are many was to get it for free (credit cards etc...) and it is worth it -- dont wait on line and just go -- pick the car you want from the isle and be done with it.
--Jim