Having "programmed" for nearly 35 years I would say that, with all I know now that I wish I had known then, go functional, at least part of the way to start with!
If I had to point you at some languages to get started with I would say:
LISP (or Scheme and there is Clojure which gets you into JVM arena)
(A sad day for LISP people today, its creator passed away today... http://www.guardian.co.uk/technology/2011/oct/25/john-mccarthy)
or
Smalltalk, specifically Squeak as it is very well supported and also has e-toys to play with which can help to give a grounding in programming basics.
Why those two? Simply because the syntax is so damned simple to pick up... LISP dialects have exactly ONE syntax rule to be learned and Smalltalk is a close second. IIRC, Smalltalk only has five reserved words: self super true false nil and the entire language is based around sending messages to objects.
In LISP the syntax rule is this: (function arg1 arg2 ...argN) and that's it!
So, when learning the "concepts" of programming for the first time I would say that it frees your mind to not be fighting the compiler or interpreter for your chosen language by making sure they are very easy to work with. Java or PHP have a lot of reserved words.
Once you have picked a language, start hacking furiously until you understand the simple concepts such as variables and bindings, functions, I/O etc. My way of learning a new language used to be to write a version of "Pong" as you need to know how to read keyboard, save and load high scores, draw stuff etc.
Start small though, even printing 2+2 and getting the right answer feels good.
Then get the user to input numbers.
Read a list of numbers from a file, print the sum of those numbers.
Build on small successes all the time and if you make an error, enjoy figuring it out! I found that the more mistakes I made early on the faster I picked up the language I was learning.
Best of luck, it's a lifelong learning process!
:)