My main question is, since the PS3 doesn't play many files natively, PS3 Media server has to transcode files on the fly most of the time. My library, as of now, is mostly just standard definition files but I am slowly moving to replacing them with 720p MKV files.
Seriously consider replacing the PS3 (as a media player) with a Raspberry Pi running XBMC - it's a better user experience (better UI for sure) than you get on the PS3, and plays pretty much everything (including 1080p/DTS) without transcoding. There is an official Android remote control for XBMC too.
I've got both a PS3 and Raspberry Pi running the OpenELEC distribution, and the Pi wins hands down. Obviously the PS3 is still better at gaming!
Would the newer N54L be a better choice? Will I need extra ram to do this?
The N54L will always be a better choice than the N40L, provided you have the cash to pay the difference!
Though if you go the Pi route, you don't need transcoding, in which case the N40L will be just fine. I actually use another Raspberry Pi to run Sickbeard and other network services, running only a MySQL instance on my N36L (for a centralised XBMC media library). The Pi as a server is much easier to maintain than the custom plugins you normally get on NAS boxes, and it works just fine - it's even powered from the USB ports on my N36L!
Extra RAM is always a good idea, particularly on a NAS as the extra RAM will be used to buffer data which will increase your network performance. 8GB (2x4GB sticks non-ECC) is about £30, and well worth it.
And what O/S would be recommended for what I wish to do?
FreeNAS and NAS4Free both offer ZFS which is an excellent enterprise software RAID solution. unRAID offers an alternative software RAID solution. All are very capable, flexible, free and will boot from a USB memory stick (so you don't have to mess around with a dedicated OS HDD).
Lastly, since I'm on a budget, if I can only get a couple of drives right now, how easy is it to add ones later on?
With ZFS you could create a two-drive mirror, and then later add a second two drive mirror as an addition to your first two drive mirror. Though backing up your data then creating a 4-drive RAID-Z1 volume (single disk redundancy) from scratch would be my choice if you can.