Turns out one character made the difference:

    execute as @a[nbt={SelectedItem:{tag:{Enchantments:[{id:"minecraft:riptide",lvl:3s}]}}}] run effect give @s dolphins_grace 1

Apparently, enchantment levels need to be indicated with the letter s behind them.

Also, the command to works fine with additional enchantments, in a singleplayer world. On my PaperMC server, however, additional enchantments make the command fail to register. I'm looking for a way to get around this. Worst case, I have to add all possible combinations of enchantments including riptide.