I'm using Debian, almost anything should run/compile on it. In the first place I only want to be able to sync the thing with my PC locally, connecting to my remote server would only be a nice extra (I use a cheapo prepaid card from a noname provider anyway, so I suspect that they support the minimum of current technology). Let's say maximum price is 400$, though I would pay more if the quality is really good. From my Linux experience I have learned:
Good software is free, good hardware expensive!