Good places to start with simple game development

Hey guys,

I figure you're all pretty knowledgable and I feel my Java skills increasing, so I want to try my hand at game development.

I by no means expect to write the next Call of Duty or Battlefield, or anything complex. Nor do I expect it to be a fast and lucrative process.

I do, however, want to make a simple, low-graphic FPS style thing. Something along the lines of 007 Goldeneye on N64 would be a good target. To be honest, world design is the bit I'm looking forward to the most but I'll focus on that later.

The main thing I want to know right now, is where should I start? What software packages are good? I've looked briefly at Unity, but it looks like it might be restrictive further down the line as so much of the core is already written (I may be wrong there?).

I'm not excessively fussed about the language I use for it to be honest, I'm doing this to learn new things so a new language would be interesting!

As for platform, I'd like to run either on PC or Android. I've got myself an Ouya (well, a present for my 21st Birthday) so I'd love to be able to eventually release something on there.

Anyone got anything to guide me?