Honestly, no, Photoshop ISN'T your number #1 option.
First, Photopea is a free in browser Photoshop replacement. Totally worth it to just use Photopea if you're a personal user, as the interface is very similar to Photoshop and will get you acquainted with how it works, but it is simpler in many ways, while having the basic photo editing tools you'll want to put text on a map. I now make this one of my first recommendations.
Instead of Adobe programs, I use Affinity Photo and Affinity Designer now, which are up-and-coming suites for graphic design quickly drawing people away from Adobe due to having features such as 'filter layers' which can stay intact, making your file ultimately more editable.
For my primary illustrations, I use Clip Studio Paint, as I really like its brush tools and stabilizers. I am not using free brushes, but purchased brushes from Flyland Studios and many I've made for myself specific to cartography.
For brushes, consider downloading KMAlexader's brushes. He participates on the forum and you'll find those easily. He has some very nice historical map sets.
For converting sketches into vectors, I use Super Vectorizer 2, which was a cheap program I grabbed which has saved my butt on numerous occasions, because it works EXCELLENTLY to take a sketch and turn it into vector lines, far better than the in-Illustrator converter, I found (which of course I have now replaced with Affinity).
Recently I've begun integrating Other World Mapper into my process, a single-time-purchase as well, or I wouldn't be using it. This program is still in beta, but astoundingly useful for mapping. I would recommend it over Photoshop for a new map maker by leaps and bounds. While I do not feel someone is going to be 100% happy with JUST OWM, because I definitely found myself wanting to make my own assets, textures, and apply photo editing filters, out of box, with just a mouse, literally anyone can make a decent looking battle map.
Just for funsies, I did a screen recording of me making a fantasy country map in Other World Mapper (which has been sped up from 5 hours of work to 5 minutes of video), using only their tools, making up a section of mine and my co-writer's world on the fly. I pre-planned 0% of this map. No names (except for 'Estavin' and 'Garador Ocean') existed in the lore before now, and the shape of the country was a vague thing in my mind. So you will watch me make up part of a world using OWM's tools here, and observe that part of the way through, when I change my mind about some things, how easy it is to add and edit those parts of the map. These aspects are why I feel it's one of the best budget-friendly programs for a new map-maker.
I understand people like freebies too, so I maintain a list of as many free fantasy map and dungeon generators as I can find. A lot of my clients come to me with maps from these generators as their 'sketches' and I edit this specific blog post link whenever I find new free tools for map creators.