Try using the generic.avi.h264.audiocopy profile and set the resolution at 720 x XXX (PAL) or 704 x XXX (NTSC) or as close as you can. I am pretty sure that this will work on both devices.
Then, as a test, encode only a chapter or two of your favourite test movie changing the bitrate. Start at 1100 and then try it at say 500 increments up from this.
Then, play the original and each of your tests and see which you regard as acceptable.
As has been said many times before, this appraisal is VERY subjective, so you have to find what YOU are happy with.
