Discoverability is probably the second biggest hurdle when it comes to developing a game (the first is actually having something to publish)
So, title question. I know I could try to throw money at Instagram, TikTok and Youtube (know your target audience), but I think using their built-in advertising is more likely to miss than hit. Youtube is even more problematic, as a significant portion of people smartly avoid their ads (either with extensions or watching from piped or invidious).
Maybe paying to be on top of itch.io might work somewhat? I'd like to know from someone who did that, what was the turnout (number of sales/downloads per number of clicks)
One thing I think about is getting in contact with a number of small-ish (2k or less followers) content creators and work out a deal - free copy of the game, make a video being honest about it, leave a referral link for viewers to buy.
A problem of mine that I'm aware of is that I don't have much of a social media presence, not even Discord servers, thus I completely lack any sort of "organic digital voice".
I really want to know what are some decent strategies that a solo person could attempt to get some attention for their own game, and maybe the prices/budgets needed.
Besides throwing money at a third party, you could just do it yourself. I don't really use TikTok anymore, but I used to see a lot of "Watch people program" style TikToks where developers show their game in progress, together with some explanation of something challenging they recently build.
If your game is cool, showing some "In progress" / "Making off" videos gets people excited about the game before it's release
But like you said, it depends on your target audience. Something like that would end up in the algorithm for "Programming TikTok".
On tiktok, what might work is showing off silly stuff possible with my game, or close calls that end in failure, as that tends to get people to rewatch the video and share. Wouldn't fall into programming content, but "funny", which has a huge audience.