How to Replace Excel?

We are getting to a position where the entire business will choke on Excel. We are growing rapidly, large contracts coming in left and right. We deal with the government,so often Excel is all they know. What can I use for quick deployment, multi user access to make it a bit more manageable?