If I were to make the suggested modifications would the whole thing be ok in such a scenario?
I would think so yes. But if I was building it I would power the Arduino from the same 5V power supply as the LEDs, apply the voltage to the 5V pin. Is their a reason why it has to be connected to your computer?
Afaik resistors don't have anything special, just how much Ohm of resistance they provide,
Anything from 220R to 510R ( that R means ohms ).
do I just search for a 1000uF capacitor or is there something else I need to look out for? Do they differ by voltage or something?
Yes they do differ in voltage but you will be hard put to it to find a capacitor which takes less than 6.5V which is the minimum voltage you need for a 5V supply. ( the voltage plus about 20% margin ). Bigger voltage is better but they are more expensive and physically more bulky.