Then there is your travel style or your expectations. If I were in a small city like Krakow, I would be on the road a lot as the city is too small for more than a week or two (for me). Being on the road a lot is cost. I've been in Budapest for about 3 years now and have yet to run out of new neighborhoods, markets, architecture, history, etc to explore. The city just never ends. BUT, I also like to travel and for that other than Austria and Germany and Slovakia for my patients on a train ... well ... I must fly. I suspect Krakow has the edge on train travel.
Fortunately, Budapest is well served by the discount airlines. Not many places you can’t reach in under two hours and under $50. Between Ryan and Wizz you can reach all of the conventional Western European destinations cheap, fast, easy, but what has been most interesting for me has been the old communist bloc countries and a few unexpected destinations: Albania (Tirana), Armenia (Yerevan), Azerbaijan (Baku), Bulgaria (Bourgas, Sofia), Croatia (Zadar), Cyprus (Larnaca), Georgia (Kutaisi), Lithuania (Vilnius), Czech Republic (Prague), Moldova (Chisinau), Poland (Katowice, Warsaw, Gdansk, Wroclaw), Montenegro (Podgorica), Romania (Brasov, Bucharest, Tigu Mures), Turkey (Antalya, Istanbul), UAE, Jordan, Israel, Malta, Morocco, and most every destination in Western Europe.
If you are going to use Krakow, then I suspect your tourism side trips are going to be mostly Slovakia, Czech Republic and Poland and those are very interesting and beautiful destinations. Do check the train times as there are some mountains that create some longer journeys. But I suspect that train travel has more options out of Krakow than out of Budapest. A whole world out there to explore. In the event you want to move a bit further away for a trip, check the discount airlines that serve Krakow and see where they go. I did a quick look and the coverage is pretty good.
Finally, cost. I hear good things on prices in Krakow, but I suspect Budapest is less expensive and if you are spending more time exploring the city then that would keep costs down too.
Another location? Again, it depends on your expectations. Montenegro but I wouldn’t do it without a car, the same with Croatia; but with a car there is a whole amazing world in the Balkans.