So I found 2 places that could book my cruise for me in bitcoin.
The first
http://www.southafrica.to was decent but they're based out of South Africa and I think the currency exchange added a few percent to the price so their price was a few hundred dollars higher.
The one I ended up using is
http://shipsandtripstravel.com. After getting the cruise picked out they sent me the payment form and I chose "cash", then the agent wanted my credit card for the deposit and I told her I don't have one and I can only pay in Bitcoin. She talked to her manager then came back saying they don't accept bitcoin as payment.
So I replied to the e-mail with this link from their webpage:
http://shipsandtripstravel.com/lagniappe/bitcoin-travel/The post is from January 2014 so they obviously set up the payment a long time ago and haven't had people pay in bitcoin since. She contacted the IT guy and he sent me a BitPay link for the payment.
I contacted about 20 different local agents in Florida asking if they'd accept Bitcoin. The only ones that replied said that their franchise contract only allows them to accept credit cards or certified check/money order.
I did some research and found that I can pay cash for stuff on the cruise ship, you just deposit $500 or so for the week and pay at the end. I can use localbitcoins when I get back to the US to get cash, I can even use localbitcoins at the small islands so I can pay for things in the local currency (which is usually cheaper).
Now to start contacting companies about paying for excursions with bitcoins