if the midtones and highlights are great (i.e. exactly as you wish), another paper grade wouldn't help you.

Sometimes it is hard to decide whether there is enough shadow detail on a negative or not. Try dodging at least one shadow area to determine whether you can pull someting out of the shadows. If that helps, your negative is simply too dense and you may try dodging all shadow areas. The suggested N-1 exposure and development would have helped in this case. However, you may find it difficult to apply N-1 equally well to all pictures on a roll of film. And you can't apply this afterwards. Masking the negative would help, too. But I would not suggest that to a newbie.