A Vehicle Rental NPC exists in each racial starting city - but not faction HQ starting cities. Location varies by city, so you essentially need to walk around until you find it, but it is conveniently named "Vehicle Rental" or something equally obvious.
But I thought they should be now in all starting cities. An automated script was supposed to do that or something. To be sure you don't miss him, click on "SCANNER", and scroll slowly and carefully through the full list of 50 or 100 NPCs and PCs you will be able to see the "Vehicle Rental".