"I think this could be optimal: Video: MPEG-4 AVC Audio: AAC (Faac) Format: MP4" - correct, I think so too. AVC decoding is now in every gpu (nvidia, amd, intel), in every bluray player, and in every ios/android device (plus of course open-source support in ffmpeg), which means very nearly every multimedia device today. AAC similarly is the standard for iTunes and in almost every device. MP4 (or 3GP/mov variants thereof) are probably the most widely supported container other than MPEG2 transport streams. So this is a good combo :)
The devil is in the details of AVC settings. For widest compatibility, use Main (or possibly Baseline) profile, the lowest level that matches your resolution/fps, 1 ref frame, no B frames. This should be compatible with any legacy devices (as long as they can handle the resolution at all) and understood for many years in the future.
The answer in the library world of video archival is different: they seem to be converging on MJPEG2000 and MXF.
See: http://developer.android.com/guide/appendix/media-formats.html
Video file formats supported in iPhone
http://www.archives.gov/records-mgmt/initiatives/dav-faq.html
http://www.digitalpreservation.gov/formats/content/video_preferences.shtml