Size is not an issue (they will come out at whatever size the screen is) but resolution is.
You don't want the resolution to be lower than the native screen resolution as they will look fuzzy and you don't want them to be higher resolution than the screen because the phone will just waste processor power resizing them.
Consequently, the ideal resolution is the native resolution of the SGS2 screen ie 800x480.
I am assuming here that you are going to watch them on the phone itself, not with an HD monitor attached using the MHL cable. If you are going to do this, they ought to be full HD ie 1920x1080.