Cocoa Beach is the town that is right next to the cruise ship terminals - "the Port."
We rented our car from the National office in Cocoa beach, which is several miles away from the ship terminal and only about a 10 minute cab ride. It is the furthest from the terminal, but by only a few miles. Being in a cab, it did not matter to us which rental place we were going to because it is not a significant amount of time, and it was so quick once we got there.
We enjoyed having our own cab, paid for by National, and will do it again. The driver told us that Yellow Cab has a contract with national - $11 per run. National found it cheaper to use cabs than to keep and maintain their own van.
Check Dave's site for map and location of rental car places.