DVD
The first thing you should do is speak to your company's HR dept - you never know what may arise - a conflict of interest, for instance if another company in your mega-corporation does business with a similar shop.
Stay away from tapes if you can. DAT tape drives in particular have caused me no end of problems. DVD writers are now cheap. If you're looking at < 4.7 GB after (g)zip, then it may well be your most cost-effective solution.
One thing I haven't seen is documentation and training. It sounds like the users are totally non-computer-literate so you're going to have to budget cdonsiderable time here. Remember the KISS principle.
