Why should the first letter of a Java class be upper-cased? Is it not possible to run a program containing lower-cased class names? If it is possible, what's the difference?
It's a coding convention, adopted by most Java programs. It makes reading code easier as you become use to a given standard.
No, you don't have to follow it, but you won't make any friends by not doing so ;)
Why / how was this convention established in the first place?
The convention was established by Sun/The creators of the Java language.
It was likely establish to improve the promotion of the language across a wide and diverse audience, to lower the entry level requirements for new developers (much easier to learn if you don't need to keep switching between other people's "ideas" of what good code looks like) and generally to try and keep the code clean within the community.
You could ask "why do companies have style guidelines for coders?" and the reasons would, generally, be the same