It's even more complicated. I grew up north east of Oslo, but speak close to western Oslo dialect with some now pretty-conservative Bokmål use (to the point where your rendition of Oslo-dialect is entirely different to how I speak - e.g. I prominently pronounce the "l" in "skal" and my pronunciation of "kirken" has nothing resembling any "sh-" sound), partly due to my dad, partly because I grew up reading a lot of old books.

At school we had an exchange student from Germany one year who quickly learnt to speak the local dialect, not too far from your rendition of Oslo dialect, but more -a endings, e.g. "kirka" rather than "kirken", but she struggled to understand me, because of those differences.

Those dialects are a 15 minute train ride apart.

People who grow up in Norway will understand multiple of these variants without necessarily being entirely aware of how different they can seem to foreigners, exacerbated by the fact we tone down the differences a lot in writing - in particular spoken Norwegian merges a lot of words. E.g. you can find people saying "skarru bli med?" ("are you coming?") while writing "skal du bli med?". But even those speaking forms of Norwegian close to conservative Bokmål like me will have pauses that are surprisingly short between some words - e.g. I have a gap between "bli" and "med" in my example sentence, but it's short enough that it's not a given it's clear for non-native speakers that I'm saying two words.

And despite the destigmatisation of dialect use in recent decades, a lot of the spoken Norwegian dialects that today deviate from both Nynorsk and Bokmål are rarely written down except in dialogue in novels, and even then it's politics - it's more common for more radical Norwegian writers to write dialogue in dialects (ironically, several of the most radical older Norwegian writers promoted Riksmål / conservative Bokmål - e.g. Arnulf Øverland was both a member of the communist Mot Dag - "Towards Dawn - and a president of the Riksmåls-association), making it even harder for foreign learners to get exposure to them during study.

To your issue of understanding people from Eastern Norway, in a reversal I still recall an embarrassing moment on holiday in Denmark as a child. I mostly understood spoken Danish (the article is polite and say they sound "blurred", while the old common joke is that Danish sounds like Norwegian spoken with a potato in your mouth), but at one point some kid was trying to talk to me at the beach, and I apologised to him, telling him I didn't understand his Danish very well.

That afternoon I learned my mum had talked to his parents, and the family was Norwegian, from Bergen, and most certainly not speaking Danish. I wouldn't mistake those two today, but he spoke differently enough to me that as a child guessing he spoke Danish was not a big leap.