Depending on how far you want to go with your learning, it will pay off to learn the object-oriented principles of a language like C# or Java sooner than later. Once you master those it becomes much easier to pick up other languages (like PHP). I did the minimum to get by in my intro to programming class only to come back and re-study all the material once I decided to go into computer science. I've heard from coworkers that the "Head First" series of books (like Head First Java) are very helpful for self-teaching.
Having said that, there's something to be said for the practical approach of tackling problems and areas of interest as they come with a dynamic language like PHP or Python (or plain ol' HTML and Javascript, for that matter). It's helpful to have projects that you care about where you can see immediate results to maintain your enthusiasm for learning.
But learning the concepts of computer science (algorithms, logic, internal workings of the network and hardware) will certainly help in the long run and will make you a much better programmer if you decide to stick with it. I don't have any specific resources for this, but maybe other posters will have some to share.