I would try to learn the concepts of object oriented programming (OOP) before I picked up a language (assuming you've got the core programming concepts understood: variables, conditionals, loops, and functions). I don't have a good reference for learning "pure" OOP (and in fact almost any reference is going to use sample code in some real world language).
Trying to learn a modern language before you understand OOP will leave you not fully understanding why the languages are the way that they are. For example, when you get to collections of objects in Java, you'll probably be very confused when they keep talking about Lists but you find that the compiler won't let you create just a List. Then you'll find the ArrayList and start using that, but then you'll ask yourself "why would anybody mess around with List when you can just use ArrayList and have it work?". At that point you'd be missing the entire point of OOP.
Once you grok OOP, I'd go for one of Java, or C#. After that I'd learn about how the browser cycle works (HTTP requests, responses, that kind of thing) and then pick up PHP or ASP.
I would never bother with C unless you were looking to write a compiler, an operating system, or very low level embedded code. There are things which are perfectly moral (and necessary) in C that are the equivalent of inhuman crimes in more modern languages. For example, in C it is not unheard of to take a pointer, figure out some arbitrary number of bytes away from that pointer, start grabbing bytes from that location, and cramming those bytes into some array somewhere. In Java, C#, PHP, Ruby and other modern languages doing that would crime against humanity because it's asking (more like begging) for your code to crash.
And of course, bottom line, Android apps are written in Java (though you won't necessarily have access to all the same stuff that you do when, say, you go through Sun's Java tutorials).