"Most Android Apps are written in Java"
Java is simply a language. Oracle Java SE is a well-known example of a Java VM or runtime environment that is also colloquially referred to as 'Java'.
"and the ADK has mostly Java interfaces"
Google copied Sun's Java API in their own implementation of the language and runtime. This is the basis of the infamous Oracle lawsuit.
"how does Android not run Java?"
Android runs ART, which in turn replaced Dalvik found in older Android versions. These are both Google's own creations and are unrelated to Oracle's JVM products mentioned above.
The poor security reputation for Java largely stems from the browser plugin included with the desktop versions of Oracle's JVMs (and it is pretty bad), but this has unfortunately extended across much of the industry to tarring anything remotely involving the name 'Java' with the same brush. That said, this latest run isn't helping. :)