To decode H.264/HD, you need a reasonably powerful CPU (software decoding) or a GPU that can help out (hardware decoding). It's not a tvheadend issue, as that is simply shifting bytes from one place to another - it's turning those bytes into graphics that's the problem. Most applications will use ffmpeg/libav.
Recent Android devices supporting NEON and the latest XBMC Gotham builds should work. I don't know about the Pi, but I thought it could do it - XBMC 12.3+.
Generally... not sure about Debian, but Ubuntu tends to stick with old versions of software as time goes on, and you need to upgrade manually (add the PPA) or upgrade to a later release to ensure you get the later (arguably 'better') code.
Your alternative is to transcode - read elsewhere as to how to enable that in tvheadend - but that will need a powerful system again.