I've been the 23 yearold on the company trip and sometimes you just don't want to mention that you're that young but in the case of a relo they should know this coming in and have something to offer up.
If not, enterprise always rented 18+ when I needed a car. You can prepay it so there's no shocker at the door.