I am curious about the Program-Erase cycles
Long story short, NAND flash memories can "drain" individual bits from 1 to 0, but not the other way around. For that, you'll have to re-set all the bits of the page, then clear out the corresponding ones.
In a write cycle, re-setting the whole page (with 1s) is the "erase" stage; this is what takes most of the time and causes wear to a page. The "program" stage is simply clearing out (from 1 to 0) the neccesary bits in order to create the intended data to store.
is the size of them always 512Bytes, in all microSD cards no matter the card's capacity?
(meaning this 512 number is defined by the manufacturer of the microSD card, in hardware)
Not entirely sure. Either these boundaries are defined by the built-in controller (the chip who actually "talks" with the Arduino or any other card reader), or it's the actual (physical) page size of the memory itself.
In SDSC (cards up to 2 GB), it's actually possible to change the block size to a smaller one (although it's done virtually by the card's controller), and write a single byte like an EEPROM.
However, in SDHC (4-32 GB) and beyond, this is not possible anymore, and the block size is always fixed to 512 bytes.
Or is this number affected by the user somehow, for example when Formatting the card?
(from what I remember from Format programs, you can only choose the Cluster size, not the Sector size..)
No, that's something defined by software (high level); the sector size is indeed defined by hardware (low level).
In digital mass-storage devices, a cluster is just a software-defined group of contiguous hardware-defined sectors (hence its name), in order to simplify some the free space and file allocation management. Larger clusters means less filesystem's data structure and processing overhead (which may also translate in support for a bigger volume/partition), but at the same time potentially larger "slack" or "internal fragmentation" (wasted disk space, unusable by the filesystem) in small files.
That's why you can change the cluster size, and not the sector size.