A Muni can be a bit overkill (heavy) for city riding, but it really depends on how you want to ride. A typical Freestyle tire, being relatively skinny (by outdoor unicycle riding standards), has to run high pressure to keep from bottoming out on potholes and such. This makes for a harsher ride and higher difficulty level in rolling over things, as you have noticed.
You mentioned a 24x3" tire, which would be a huge departure from what you’re used to. It’s all about tire volume. the fatter the tire, the lower you can run the pressure, and hence the better rollover and bump-eating qualities. A 24x3" tire is close to the same diameter as a 26" “typical” mountain bike tire. If you get a 26x3" tire (make sure the uni can fit it), it’ll again be bigger, close to 29", and heavier.
Very different. It’s all about volume and air pressure. You don’t really need a Muni tire for city riding, unless you occasionally want to stray off into the mud somewhere. That’s a lot of tire to carry around. I’d recommend a fat “cruiser” tire, like the kind you see on beach cruiser bikes. These are still heavy, but should be lighter than a dirt tire because they leave out all the knobs. On Unicycle.com they have a cool-looking Kenda Flame tire, at 3" wide, which is still probably heavy but looks cool.
This is where 26" is an advantage over 24"; tire choice. You have zillions of choices in 26", and waaay less in 24". If your goal is to cover distances, in the City, I recommend 26", or possibly 29". For 29" you can get the Schwalbe Big Apple (that’s appropriate!) tire at 2.0", which is an excellent tire for pavement. If I wanted a NYC cruising cycle, I’d get a 29" with that tire. And I have ridden in NYC before, though always on a 24" Freestyle but we didn’t have all these choices in the 80s. I also rode a 45" hard-tire big wheel, but that’s off-topic.
The Schwalbe, or another not-so-heavy tire will give you better volume, but still be lighter and quicker than any dirt or super-fat tires. Don’t let your being a beginner push you into a cycle you might not enjoy as much as your skills improve. But if you think you’d prefer an easier cruise on a heavier wheel, consider that Kenda Flame tire on whichever size wheel it comes (24 and 26, I believe).
Not sure how you can disagree with a 29" being smaller, or more maneuverable for that matter. I think what you’re saying is that a 36" can be quite maneuverable if you want it to be. This is true, but it’s always going to be quite a bit more sluggish than a wheel that is smaller and lighter. This is true for any up-sizing you do, assuming the weight and tire type is proportional. What you don’t get in Michigan so much is crowded sidewalks (okay, maybe on campus). In NYC I had a lot of fun zooming down crowded sidewalks on my 24" back in the day; something I probably wouldn’t do nowadays. At least not as fast.
Resv, if you can, go ride with the NY Unicycle Club and see if you can try out some different wheel sizes. Ride them over some bumps, make some turns to get a feel for them and it can help you decide. Also remember that your skills are going to keep improving. Especially if you keep riding on NYC streets and sidewalks! Plus you’ll get even more opinions from the owners of those unicycles.