It is unwise to judge too early seeing as both you, the damage-dealers, and the tank (in dungeons) are all likely levelling up – all of which typically leads to more pressure on the healer than anyone else. Lower damage numbers and squishier than average tanking = you’re the one who’ll be working harder, whereas your life is infinitely easier with a sturdy tank and good damage to make fights shorter. That’s typically how the trinity works, so it can be very easy for people to fall into overall bad group (repeatedly) and have their opinion tarnished. Furthermore, levelling is always going to be spiky because of scaling, but I never saw the problem (and I say that as someone who levelled three different Shaman, primarily as Resto from 1 to 120).
Shaman are perfectly fine for M+ until higher keys - at which point their reliance on long-cast boils down to needing more coordination compared to other healers. Our strength is mostly AoE healing rather than single-target, which is why Shammy is more desirable for raiding as they can pump out impressive throughput and have desirable raid-buttons. There are various essences in BFA that can help with the single-target issue, albeit they are typically cooldown based or RNG/proc based, ie. they’re not going to ‘fix’ the problem, just help you deal with it slightly.
I just finished levelling an alt Resto Druid and I can tell you that I prefer my Resto Shaman in most content by quite a wide margin as far as Healing is concerned, but that may be my comfort-zone bias. I’ve played multiple Shaman over the years and it’s still the class I always fall back on in the end, so I’ll be sticking with it in Shadowlands.
Regarding Healing Surge: That is the panic button. It is not meant to be spammed as that is a one-way ticket to going oom (and mana is one hurdle you will have to learn to deal with in end-game), though there will be plenty of situations where you are reduced to spamming it by necessity. The other (Healing Wave) is your efficiency button - the one you use when people need topping up but aren’t in immediate danger. It’s slow, but far less costly.
Regarding Prot Paladins: They’re easy to play and smooth to level, but also very easy to play “badly”. Prot Paladins won’t be very tanky if a) They are outside of their Concecration and/or b) Use all their Shield of Righteousness on a whim. A lot of Paladins levelling up will just lash out all their SoR charges to do damage (and probably move out of their own consecration a lot), meaning they don’t have much protection without sacrificing proper cooldowns. A lot will also waste their self-heal, and playing Prot Paladins in such ways leave very big windows where they’re prone to being unmitigated.
Still, a really well geared Paladin who knows what they’re doing are one of the most comfortable tanks to heal if you ask me. I’d much rather that compared to Monks or Demon Hunters. Prot Warriors seem to be the go-to, but they have little to no sustain at all and far less versatility compared to a Prot Paladin.
In short, the issue goes in both directions. To truly answer you, people would need to know what you wish to achieve with your Shaman. Eg. Raiding, M+ spam, PvP… or some/all of it. I wouldn’t judge it too early, but if you’re really not having fun with it now, I can’t see why you’d magically have more fun with it later. Shaman are in an average spot - and have been for a long time.