Here's the Wikipedia category Theoretical Computer Science. It will give you an idea of all of the things that you can learn in a 4 year program.
In the top, I can see most of the things that were mandatory.
Analysis of algorithms & Computational complexity theory
Theory of computation (Combinatorics, Discreet math, Numerical methods)
Logic in computer science
There is more to a CS degree than just learning how to program (a lot of proofs), but it is all very useful, and pretty fun, once you get into it.
As for how 'hard' the program is, it depends on the school, and your professors. Some classes were very hard for me, but also very fun. Other classes were hard because the prof had an incomprehensible accent or some other small reason. If you have an aptitude for logical, analytical, and creative thinking, and like to learn, you should be fine.
You can tell if this is for you if, when you were programming PHP, you did a lot of research into how to make your code faster, and were naturally drawn to looking under the hood - going into the source of PHP, mySQL, and various frameworks, trying to understand 'why' when people told you things like 'quicksort is the better than bubble sort'.