What settings are you using to encode your file (resolution, frame rate, data rate, audio settings, etc.)?
You're not the first person to complain about this with an Android device. Not every manufactured Android device has a dedicated h.264 decoder chip on it. So many have to rely on the CPU to decode and it is a resource intensive decode. You may have better luck transcoding to a WebM or Ogg Theora format for use on Android devices (again...depends on the device).
Not to make this an iPhone rally-cry post more to highlight a difference, but Apple in 2008/2009 started to embed a h.264 decoder processor on the main board of the iPhone. So instead of using CPU cycles to decode the video (battery intensive) the dedicated chip handles the h.264 decode. In that area the iPhone has a great advantage.