What a pain and I feel it too. Went for weeks looking everywhere for a solution. I too streamed all my movies from my computer -- that was not an issue as long as it was say a 700 MB dvix avi. If I tried streaming a high quality or full quality video it was laggy using Tversity. The issue I had (maybe yours) is that my computer holding all my movies is in my office and the PS3 is in my living room. The computer is connected wirelessly but at least the PS3 is connected directly to the router since that is where the modem is. Still the issue was that I was sending the movie wirelessly from my comp to the PS3 and even with N mode, I still could not send a high quality MKV or full DVD without lag.
Anyhow -- a few options:
Since your external drive must be formated in FAT32 for the PS3, make sure it contains movies that are all in VOB format. Most programs (like DVDFAB) will rip from a cd right to a dvd folder and have your autdio_ts and video_ts folders. All the movie files inside (.vob) will be around 1GB. My PS3 has no issues playing these files.
ORRRRR and this is what I do, i sadly convert all my movies, ISO's or ones in the Video_ts folder (VOB) using a free program called Handbrake (google it), and it has a setting right for a PS3. I tell it where the DVD is or the video_ts file for source file, where I want the output (external drive), I choose the MPEG-4 (ffmpeg) video codec option (fastest), best sound quality that is supported, and I cue up 20 movies on my computer and off I go. It takes roughly 8-9 min for each 4.8 GB movie to be converted. Once done the movies are roughly 2 GB in size in MP4 format which the PS3 has no issues playing. I then either transfer them to my external drive and connect it to my PS3 or stream them. These 2 GB files actually dont lag for me.
If on the other hand you have downloaded say a HUGE movie and it's in MKV format, you can use the free utility MKV2VOB and convert that file to a VOB directly. There is an option to break the VOB files into smaller than 4 GB chuncks just for the PS3. In fact this app was mape for PS3 owners. THen once done, again transfer these finished VOB files which are less than 4GB to your external drive and off you go.
One other things, if you PS3 is directly connected to your router (like mine is), make sure you set the speed of the network port (in the network options of the PS3) manually to 100Base T full duplex or 1000Base T Full duplex (if your router supports it). Do this rather than AUTO -- for the life of me it was so laggy before and then I manually set all the options for Network in the PS3 and I can now stream to it again large MP4 files up to 2 GB or so.
One last option which I never bothered with is that if you can stream a movie to your PS3 say using Tversity, you can also "copy" that movie (hit the triangle when you see the movie) to the PS3's internal drive. If you have a large drive version of the PS3 (I have the 40GB) you can copy whatever size file directly to the PS3's drive. Takes for ever though on a wireless network.