Creating Kindle-friendly versions of existing LaTeX documents

This will only be possible with a lot of manual intervention. (Many arXiv documents use plain tex or context or amstex instead of latex. But your question specified latex, so I'll assume that much.)

The main problem is that tex isn't very good at doing fully-automated typesetting. In particular, it will not rebreak displayed equations to fit with your new margins. It also has a pretty perfectionist view of regular text. It will try to set what it thinks is a beautiful paragraph, but if it fails then rather than making a compromise paragraph it will just give up and make an underfull/overfull box for the author to deal with (by rewording the paragraph, by adding explicit \linebreaks, by telling tex about additional hyphenations). This isn't a problem when you're editing your own paper, but it's very bad when you want to batch convert a large number of documents in an automatic way. Some tricks are discussed in this FAQ answer.

However, here are partial solutions to the problems you pointed out.

Resolution

Tex generates DVI and pdftex generates PDF. Both of these are resolution independent. If you want to convert to a bitmap format, then you can use something like pdf2png (slow) or dvipng (fast).

Margins

The geometry package gives a lot of control of margins.

Figures in grayscale

Figures on the arXiv will be in a huge variety of formats. EPS, PNG, PDF, not to mention metapost code, PSTricks, PSFrag, and the latex picture environment. The standard formats can all be rasterized to a 4-bit PNG at a decent resolution using something like GraphicsMagick, but it will likely need manual intervention or some really clever scripting. Once you've got the bitmap, you need to feed it to latex, dealing with the fact that some submissions use latex (which doesn't understand png) and others use pdflatex (which doesn't understand eps), they will use a combination of packages, such as graphics, graphicx, epsfig and various journal classes with their own twists, so there will need to be some intelligent editing of the latex file. For metapost, PSTricks, PSFrag you will need more extensive editing.

Removing boxes around hyperlinks

This one is relatively easy. In many cases, simply compiling the arXiv tarball will do this already, because the arXiv uses hypertex to add these links, and if you compile with regular tex this won't happen. If the authors used the hyperref you can in many cases remove the \usepackage line, or, more safely since maybe the author used some commands from hyperref, add the colorlinks option to colour the links instead of drawing boxes (you can set the colour to black if you don't even want to see them that way).

As an astrophysicist, I wrote a simple python package to process arxiv/astro-ph posts for Kindle DX, but presumably it should be easy to incorporate math posts as well, e.g., by adding common math journal tex-style files.