Fort McMurray us a great community, unfortuntately not much other than bars would be open at that time.
If you want to get some rest check out the Chateau Nova right at the airport. They have a shuttle but you may have to pre arrange at that time.
The new terminal is super, lots of food choices now. I don't know about luggage storage but if your flight is all on 1 ticket you may be OK.
If you want to go into town renting a car will be a far cheaper and more pleasant experience than a cab.