If you want to learn programming the first thing to learn is that language is what you program with, it's the tool not the skill.
The best way to learn is to use it in anger.
Something like Python might be a good start, perhaps few scripts to do various job related tasks.
An ex colleague of mine picked up programming from wanting to make use of network statistics being logged in an access database.
He did a sort of lanview type application, that showed him what the network had done out of hours.
You need to start simple, but you are more likely to self teach successfully, if you have something 'real' to do.
PHP or Ruby on Rails are only useful starts if you want to do something specifically web based. Personally I'd learn programming first.
Whether you pick up java, C#, Ruby or Python first doesn't really matter, HR to the contrary. If you can program, you can program. If the current market is the issue Java or .NET will do fine.