For us Gen1 MBA users, our choices are very limited. First off, anything less than 80GB is pretty useless these days, so you are looking for something at least 120 GB in size. Gen1 has PATA interface with ZIF plug and it needed ONLY 5mm think drives!. Anything 8mm or taller, the bottom case will NOT close. This is the space constraints.
It seems that all new SSDs are built with sata interfaces, so the pata days are pretty much gone?. I was hoping Apple pressure either Toshiba or Samsung to make limited production runs of SSDs (128GB variety that is PATA ZIF and 5 mm tall) for Gen1 users. I would pay up to $350 for this. One can get Patriot 128GB for less than that today but it is 2.5inch stat2 and 9.5mm think (not fit).
For non-SSD but HDD, the biggest size is likely only 120GB, so it is not much of an increase. The 5mm height restriction is a huge limitation to the upgrade second only to the pata/ZIF interface.
Note: There might be a "converter cable" that had pata/ZIF on one side, a sata/pata bridge chip in the middle and mini-sata on the other end. This will allow sata drives to be installed (if there is space in there).