@WillH: Can you try opening the Phone app and dialing *#0*# into your keypad? From the series of grey tiles, select 'Sensors', place the phone on a flat surface, then head to Gyroscope Sensor > Gyro Selftest, followed by Magnetic Sensor > Selftest. Do you get a 'Pass' result for both of these sensor tests?
I have the exact same problem with my S21 Ultra. I went to a Samsung Service and they changed the phone's motherboard for faulty GPS and magnetic sensors, but the issue hasn't been solved, so it's obviously a software problem.
I somehow managed to solve this issue in Maps by disabling the "Start maps in satellite view" option in settings and so far it seems to be improved.
I noticed this working when I deleted the app's cache and data, having this option disabled by default.
I use for years with different smartphones, applications that need the compass. But really the 21 Ultra has a problem with Compass accuracy and it is a shame for such an expensive phone. Unfortunately, the accuracy of the compass is not corrected by Google Maps for a long time. The problem continues for other applications that require the mobile compass. I really did not have such a serious problem with older devices than with the s21 Ultra.