Your current theme resizes the logo drastically. (The original is 1000 x 100 pixels, but on desktop it appears at 366 x 37, and on mobile it varies from tiny all the way up to 1000 x 100.) Any image you upload is going to appear somewhat pixelated on some screens because the web browser is dynamically resizing it for you.
If you want to keep the current theme, one option would be to upload a JPG instead of the PNG you are using. PNGs are great for small color palettes and transparency, but they typically don't come out looking as smooth if a browser resizes them. A high-quality JPG will "blend" the black into the white a little more smoothly so it appears less pixelated.
Theme recommendations are off-topic, but you can try browsing the WordPress.org theme directory and hit "view support forum" to see whether the author is responsive to support requests there. You may also want to look further into documentation of a theme you like to see if they have a support forum somewhere else, like their own website - that's fairly common too.
Another option if you like your current theme is to create a child theme and tweak the header.php
and style.css
files. That way you could set the logo at a fixed size and ensure browsers aren't resizing it at all.