My CS education was similar to this. Mostly theory, very little application. However I do feel that I might have learned more if I had been asked to actually implement the theories more often.

And I also agree with the degree -- most employers would have completely looked over me if I hadn't had a degree.