Probably "0603" (1.5mm x 0.8mm), but "0805" (2.0x1.3) will likely fit also.
Destructive removal is easy just put your soldering iron across the side of the led to melt both pads at once.
To put the new ones on, clean the excess solder from the pads, apply solder to one pad, while keeping that solder molten slide the LED (in the correct orientation) into place, remove iron, let solder cool, and do the other end.
Edit to add: the codes above, 0603 and 0805 are the far more commonly used "imperial" (that is 0603 measures 0.06 x 0.03 inches), care should be taken in the case especially of 0603 because that's also a common metric code for a totally different and much much smaller size, you don't want to order LEDs that are 0603 metric!