Your intuition of a conflict with politeness is basically correct. By hurrying the timeframe you are more likely to cause inconvenience to the person you are interacting with up to the point that they would have to reschedule their tasks. This kind of interference is generally considered impolite, even if you are interacting with service personnel.
However, the effect is subtle and can easily be overcompensated with inserting bitte
:
Können wir bitte gleich zahlen ?
This is perfectly acceptable in the example you have given - after all, you are addressing service personnel.
In other social settings it might more likely be considered rude.
However, you can think of situations in which gleich
actually adds to politeness. Paying right away when being served an order in a busy place might actually be welcomed by the waiter.