If you have an older home with cast iron pipes your gas line could have blockage in it or breakdown of the inside of your gas pipe line could be causing particle build up in your devices.
IF your water heater is not getting a good flow of gas and therefore is not producing a good flame, it will be limited on how hot it can get the water.
This might be especially true if the reason you had your furnace serviced is because it wasn't working efficiently and the service tech had to clean out particles in the furnace tubes.
You can have a company come out and inspect your gas lines. They can test the pressure and see if you have a leak somewhere, maybe it is outside and so you are not smelling the mercaptan (smells like rotten eggs) added to the gas to let you detect, through your sense of smell, that you have a leak.
You should check with your gas company to see if they did some repairs to their lines lately that could have knocked debris loose or be creating a low flow.
A higher than normal gas bill can indicate a leak.
If you have a gas stove and you cannot get the flame up as high as you use to, that could be an indication that a blockage could be located on your main line before the stove or low flow due to leakage.
Good luck! Hope this helps at least narrow down the mystery!