How do I choose between shredded and finely shredded cheddar cheese?
You probably want to check for the lowest proportion of added anti-caking agent (here potato starch is used).  That's the reason it doesn't melt very well.
If you're going to freeze it, you could grate a large batch of a block you like and freeze that - the best of both worlds but a fair bit off effort in one go. If I was doing a lot I'd use the grater attachment for my food processor.