Sharing Files on Network

I work in a small office (4 x new iMac's, connected via ethernet). We have converted to Macs form PC's recently and are gradually getting everything working well. My problem is with sharing files. At the moment we are using an old (five years) Netgear Network Storage Device (2 x mirrored hard drives in an box running on Linux). All the files are accessible, but access is slow (several seconds to move from directory to directory).

Can anyone suggest a fast storage method that will allow the macs to access common files quickly (hosting the files on one Mac?). Also back up is important - is a cloud based system worth considering? We are out in the countryside, so powercuts and broadband loss are fairly common - cloud may therefore be problematic.

Any advice would be greatly appreciated.