Sounds like the game description of "X3: Terran Conflict".
Pocketim: Specifically I'm interested in playing something with a non-linear focus and the ability to freely explore, while getting into combat, upgrading my ship, trading and so on. The more freedom the better.
It has a story, but you can do whatever you want. It throws you into a galaxy with over 200 sectors (connected through "jump gates") which can be explored freely at any time (some sectors are hostile). You can fly... uhm...
lots of different ships (from freighters, over scout ships and fighters up to frigates, massive capital ships and carriers), but not all of them are available for purchase (in this case you have to bring their shields down, send marines in to board the ship and "steal" it - or get the pilot to eject, if it is a fighter). You can install a wide range of different weapons, shields and missiles on your ships.
Trading is a huge part of the game. You can fly cargo yourself, or you buy ships to set them up as traders. You can build your own stations to produce your own goods (energy cells, different ores, food), which can be sold by you (or your trader fleet), bought by NPC traders, or shipped to your other stations to produce more advanced products (weapons, shields, high tech). You can even connect stations to set up a production complex (a self-sustaining missile factory, for example). But your stations need protection (pirates and hostile aliens will attack randomly) if you're not in a heavily populated sector (they're oversaturated with most goods, so they're not very profitable - did I mention that prices vary based on demand and supply?). So you have to build a fleet to fight off the evil guys. But huge ships need a lot of shields, weapons and missiles. Buying them will be hard, because they're expensive and rare. So you'll need very advanced factories with a high need of ressources.
Pocketim: So, where's the best place to start for a newbie? I'm hoping to find something that has a decent amount of depth, but is also accessible to novices.
And that's the problem with X3: Terran Conflict... It's one of the most complex games I've ever played and it just throws you into that absurdly huge galaxy without any help. The only good thing: You don't need to learn everything straight away. In the first 5 or 6 hours you don't need to know anything about own stations. You can't afford them. You don't need to know anything about fleet management in the first 10 or 15 hours, because your "fleet" will consist of just a handful of ships. It's not really important to know how to board a capital ship with marines (there's a mission in it's storyline where you have to board a ship, but this doesn't count, because it's an "auto-win") in the first 50 or 60 hours. You don't have the ships, trained marines and weapons to do this. You don't need to know much about supply fleets for your combat unit in the first 100 hours, because your small fleet will still be easy to manage.
This game is a monster. You'll constantly learn new things, even after a few hundred hours, when you build your own HQ. There you can reverse engineer captured ships to get blueprints of them. So you can build ships that are not available for purchase, which is extremly expensive, but easier than boarding them (which costs a lot of money and ressources as well, because you'll have to shoot missiles and will probably lose some ships).
Get X3: Terran Conflict. You'll spend hours in wikis and with Google (and your galaxy map, spreadsheets and hand written notes), but it's worth it. You can't get more freedom in a game. And when your fleet finally jumps into a heavilly defended hostile sector, to conquer and to hold it, you'll feel really ... ... I can't describe it... You'll simply know that YOU did this. Not any scripted event. Not the storyline. It was your hard work! Great! No other game gave me that feeling before.
