In my opinion, "structure" has very little to do with elegance. Imagine that someone uses Langauge X to write a concise, functioning program with only a few passes through the compile-execute-debug cycle, then hands it to me. I pick it up, look at it briefly, and can see immediately what the program intends to do, how it performs the intended function, and whether or not it's likely to contain bugs. That's elegance. I could care less how strict or explicit the language's syntax is.
That was Java's hallmark "feature": it appealed to purists with its extremely strong typing and explicit, verbose, formal syntax. The architects of Java felt that if you eliminated "syntactical shortcuts," you could enforce good programming practices, and thus create better-quality code. This approach is arguably successful; Java programs are certainly much less "gotcha"-prone that are C programs. On the other hand, Java fails to appeal to the way human beings actually approach a software engineering task. It provides a million classes, but virtually none of the low-level tools involved in efficient algorithm design. Languages with built-in (syntactically trivial) support for lists, dictionaries, hashes, iterators, and other algorithm building-blocks permit rapid, obvious, and correct algorithm design. Consider that the collections hierarchy was only introduced to the Java language somewhat recently, even though such structures are essentially the bread and butter of all algorithms. At least they're present now, but their use is still crippled by all the unnecessary syntactical baggage of the Java language itself.
I'll note that I used to be in your camp: I used to think Java was the greatest thing since sliced bread. I used to teach classed on it. I tried to use it everywhere, all the time. I eventually got over it and found better languages. I still find situations where Java is the appropriate language, but they're becoming more infrequent every day.
- Warren