Minor note on verbosity thing -- I think you could cut Java verbosity a lot just by shortening keywords, implicitly making things private, making inner class syntax much shorter, and providing literals for lists and maps.
I guess what I'm arguing about with Java is something similar to what I usually argue to Haskell programmers. Haskell has a very idealized worldview where your code only asks for as much power as it needs -- as a result, you have multiple lifts that give your code varying amounts of power. In roughly ascending order of power (although there's no strict ordering). These are the functions in the standard library that represent various ways to ask for "pretty please, give me {mutation support | access to the outside world | coroutines | error handling | suboxone}":
(<$>) :: (a -> b) -> (f a -> f b)
(<*>) :: f (a -> b) -> (f a -> f b)
(=<<) :: (a -> f b) -> (f a -> f b)
lift :: f a -> (g f) a
-- this one doesn't fit the mold of the others but I'm throwing in because it breaks EVERYTHING
runST :: (forall s. ST s a) -> a
These all correspond to the same *meaning*, which is something roughly like:
liftPlease :: some kind of a -> some other kind of a
Since Haskell has this worldview where you only want to use the one that has exactly as much power as you need, you have to remember four or five ways to write the same thing. (I was kind enough to spare you the Traversable and Foldable operations, which give you three or four more ways to write it.) You can kinda solve the problem in Haskell by writing everything as an (a -> (g f) b): then you only care about (=<<) and never have to use any of the other operations. But that's opting out of Haskell's worldview.
I think Java-style OOP starts with very weak primitives which often are not that powerful by themselves, and you're kinda right -- if you want to force Java to give you additional powers, you have to get a little crude and ugly, because when you do that you're opting out of Java's world-view. I think Java's builtins have the same appeal as Haskell primitives -- writing Java the way I learned to write it is kind of like bootstrapping your favorite language's data model in C, except you get a garbage collector too. You can get exactly the powers you want and no extra ones. Your abstractions are pretty close to the machine and there's no magic going on under the covers -- in exchange, all you get are vtables and your base inheritance feature is kinda weaksauce, but guaranteed non-evil.
If you don't want bootstrapping to be part of your problem, though, Java's inheritance primitives are weak and punish you for writing all the code that means the same thing the same way. (it's probably not just the inheritance primitives -- I think a lot of design patterns are reactions to similar problems that happen if you use Java naively) Its builtins are not that flexible, because its worldview is that its builtin inheritance is all you need. Sometimes you really need the trait-like formulation, and other times you can totally get away without it. I found Java really frustrating until I got used to thinking about it like that, and then I only found it mildly frustrating.
My alternative probably would have been to write all my code in a language whose default data model looks like one of the ones I bootstrap, like Prolog or Haskell. But I actually did used to write almost everything in Prolog and Haskell and I don't think they're as suitable for the general case as your generic typed imperative language. (I felt like Haskell made a lot of my problems harder, not easier, even after I was very comfortable with how it was meant to work.)