I got a poster done at UWA photography dept. The guy there is the one who started me onto Nikon DSLR !
Check their website.
http://www.graphics.uwa.edu.au/index.html
Prices:
http://www.graphics.uwa.edu.au/digital.html
Although they wanted TIFF files, the department seems to use Nikon (a D70 and D100 from memory), so NEF may be OK.
I got a poster made of the Horsehead Nebula (downloaded a 50meg TIFF off the web) and I think it cost me $70 on archival paper.
There's another place on Oxford St Leedervile next to Oxford spares. Never used them though. They claim to be able to make billboards! It's been a while since I've been back to Perth, so they may not be there any more.
Cheers - Melvyn