WDTV Live and Qnap (or Nas4Free)
I previously used an ageing Qnap Ts-201 with WDTV Live SMB boxes under each TV.
Was a fantastic setup until I got fed up with the slow speed to transfer the files to the Qnap in the first place. I believe the new ones are much better though.
I know you require off the shelf but consider this - I put together a Nas4fFree unit using a mini itx board with built in CPU, added some ram, a case and a flash drive and a simple NAS unit was built that then just required drives.
The transfer of data from PC to the NAS runs at 120MB/s ish and was a revelation compared to the old speeds.
We can happily use the 3 WDTV live we have , all playing a high def movie with no slowdown or issues whatsoever and I have yet to find a format that the WDTV does not play.
After much, much experimentation, I find that just using file shares is the best way to handle files, like others have said, ACL's are then easy to implement and everything just works.