Optimum video codec for low end Android phones?
I got H.264 (x264 encoder) to play with these settings on my Huawei U8150


Main profile
320x240 (original video was 4:3 which helps, 16:9 or 2.35:1 should become even easier to decode)
and tuned with the 'fastdecode' setting


I used ffmpeg as the frontend, as Handbrake makes selecting the "fastdecode" option impossible

ffmpeg -i "inputfile.avi" \
    -sws_flags lanczos+accurate_rnd \
    -vf "scale=320:-1" \
    -c:v libx264 \
        -crf 23.0 \
        -preset veryslow \
        -profile:v main \
        -tune fastdecode \
    outputfile.mp4


the resultant file was only 10% bigger than the one using high profile and no fast decode

I would also recommend using MX player as it actively resyncs the video and audio for those occasional slow downs it may have, but fastdecode seems to fix all the slow downs I could find.