Your data rate is probably the issue here. Laptops usually have very slow cd/dvd drives so that the stream needs to be less than the drive can read.
So, Does the video need to be full screen. How big IS IT. Have you compressed the audio as well.
An MPG 1 might be a good choice, try limiting the date rate to a little over 1.2 MBybes per second. So audio plus video should be around this number.
If you decide quicktime use the ima 4:1 audio codec for older versions of qtime. limit the data rate of the sorenson 3 to 1000 kb.
If you can use half resolution.