First up, I'm talking in the UK here so things may be a bit different. But FYI and for others that may be in a similar situation in the UK...
I have a secret clearance and I know getting a clearance is one of the harder parts for people trying to land a government job
Interesting to hear that's the case there - it's really not in the UK. I once applied for a position in government dealing with top secret data on a day by day basis. I didn't get the job (fell down at the last interview stage) but once I got past the first 3 rounds I had to be vetted as a matter of course. The process was extremely thorough and they do need to know literally everything about your life - but as a relatively normal guy that's lived in the UK all his life and never done drugs, I sailed through the process with no quibbles at all. Had I failed the drugs test or originally come from another country the process would've likely been far trickier.
I appreciate you're not really a beginner - but I'd still recommend having a look at my sticky just for the points I make when choosing a language. In your situation I'd definitely recommend both Java and C# as general purpose languages, they're probably the most widely used out of any these days.
Never touched Delphi, but I don't know of anywhere that actually still uses it. So if you definitely know you'll need it then sure, go ahead - but as a general purpose language I'd give it a miss.
One other point - certificates help, but it's experience that really counts
If you can point to concrete examples of good quality programs you've created, that will most likely help your case more than a few certificates.
Good luck with it all!