It depends what you're going to be plugging into it - whether you'll be plugging and unplugging stuff regularly, and how long the leads of the things you are using are...
Under the passenger seat could work, as could inside or underneath the glovebox.
When I bought my current car, I found that a previous owner had wired one in behind the fusebox cover (above the driver's footwell, under the steering wheel), then had permanently fitted chargers for a mobile phone and satnav to it. I removed that however as I didn't like the idea of permanently live chargers that I couldn't see!
As you mention, a common place is in the passenger footwell, often screwed or stuck to the side of the centre console - this is more visible but the easiest place to get to regularly... Similarly, you could try (depending on the layout of the car) the back of the centre console - but that may well be too far from where you'd want the leads to go.