Another trick is to designate your movies and TV shows as music videos in iTunes. For whatever reason, Apple is fine with you playlisting music videos, but not movies and TV shows--so you have to do a little trickery to make this work.
In iTunes, first make your video playlist using one of the methods I described earlier. Then select all of the files in the playlist, go to the File menu, and select "Get info". Under the options tab, change the "Media kind" to Music Video and hit OK.
One side effect of using this technique is that videos will play in both landscape and portrait orientation, depending on how the device is held. It's neat, actually.