You can go higher on the voltage rating without issue.

1) That's pretty much what I do. Sometimes I add diameter and height filters in case the space around is tight.
2) Nichicon, Panasonic, Rubycon, United Chemi-con -- all of those are high quality Japanese brands
3) Ideally you should look up the datasheet of the original cap and find a replacement with similar specs regarding ESR and ripple current. But that's not always possible. In general the big caps around the CPU need to be low ESR (or even ultra-low ESR for motherboards from around 2004-2005, these are no longer produced but can be replaced with polymers), while the small ones scattered around the board can be of any type. But it depends on the board really, Socket 7 and earlier generally use linear regulators so anything will work, and even earlier stuff may not even have any electrolytics.

1. Yea you are correct, replacing with exactly the same capacity and voltage is obviously perfectly fine.
Tho some variation is usually OK.
The next step up in voltage is common even directly from the factory.
For instance finding 25v caps on 12v duty is fairly common, but 16v is the "standard".
Normally you find 6.3v or 10v caps on 5v and 16v caps on 12v.

Lead spacing is nice to have exactly same, flush mounted caps just looks nicer.
But its not critical in any way, you can bend the legs if you have to.
And often you can find holes for different spacing once you remove the caps.

Operating temperature is another thing you can broaden your search with.
Sure 105c is nice, and if the cap is hugging a scalding hot mosfet it might even be required.
But if its not next to something really hot you can safely use lower rated ones.
And to be honest, are you really gonna use your precious retro PC in a poorly ventilated chassis placed a crazy hot room for thousands of hours? =)

2. Panasonics are good, and usually available it seems.
There's also Nippon Chemi-con, Nichicon, Sanyo, Rubycon and probably more.

3. I only use "low ESR" caps for CPU power delivery.
They cost more, and there's usually no benefit of using them elsewhere (in fact there's situation where to low ESR can actually be bad).
Manufacturers often put caps in parallel to lower ESR without having to use a more expensive solutions (like polymer caps).

4. (I added this) remember the cap height, you can have positions on a motherboard where you have limitations.
Like near the CPU socket (to allow for coolers), i guess you can ignore this if you know you are ok.
And between the expansion slots which have max height of 15mm or you will risk blocking certain cards.