I think both would work fine with Linux. Getting the extra keys could be a bit tricky though. If I had to choose between one of those, I'd take the Microsoft one for two reasons:
1 - I have had nothing but good experiences with
every Microsoft piece of hardware I had the past years (I have an ergonomic from MS myself, though not that one).
2 - Microsoft Natural Ergonomic Keyboard 4000 has the layout in a more standard way. When picking a new keyboard, I always want the "insert, home, pageup/down, delete and end keys (plus normal sized arrow-keys)" to be where they should be. Genius ErgoMedia 700 has a slightly different layout. Check these images:
Genius ErgoMedia 700
Microsoft Natural Ergonomic Keyboard 4000
Indeed, it is always a matter of preference. Maybe you can get used to the more "odd" layout from Genius than I could...