Halycon you are absolutely correct of course, multiple sources of advantage do not stack and are negated by a single source of disadvantage, so while under Cats Grace neither Halflings nor Deep Gnomes gain anything from their existing advantage on stealth, though it's useful in general for scouting and while in combat since your cleric is unlikely to be concentrating on Cats Grace 24/7. I was just pointing that out since it's why I also don't care much about the halfling reroll personally while on a crime spree.
Let's say you are trying to pickpocket something with a target of 5:
Non-Halfling, no advantage: 20% failure chance
Halfling, no advantage: 16% failure chance (1/20 or 5% they reroll, 1/5 of the time that's still a failure, 4/5 of the time it's a success)
Non-Halfling, advantage: 4% failure chance
Halfling, advantage: 3.76% failure chance
The advantage both is way more impactful, and makes the difference of being a halfling less impactful. Add in guidance and you're less than a 1% failure rate either way. Again not saying it's not spectacular - random religion rolls or insight rolls or other unpredictable rolls coming up as you're wandering around the wild or engaging in dialogue will always benefit from being a halfling, and the sheer scope of their ability is why I consider them mechanically one of the best in the game, not at all trying to say or imply that they're not phenomenal. But the more forewarning you have of the need for a certain roll, and the more you can prep for that roll, the less of an impact their ability will have, which I think is just something worth noting.