Good codec for embedded system video decoding
While I haven't implemented this myself I would suspect Google's VP9 (or VP10) to be a good option.  

Considering Android phones use an ARM CPU, the codecs and libraries supporting it should be highly optimized as they've been around for almost 10 years, and Google has a reason to continue improving it.  Plus it's royalty free both to play and to encode.

See VP9 on Wikipedia.