(This is a copy of the comment I posted above. Now an answer due to Will Robertson's suggestion.)
This addresses, partially, problem 2 described in the question. I've never seen problem 1 happen myself; then again, I haven't used lineno that much.
Take a look at ulineno.pdf from http://www.ctan.org/tex-archive/macros/latex/contrib/lineno/ (the user's manual). It explains why lineno has trouble with equations and paragraphs containing equations, and also some work-arounds.
Basically, the line number can only be computed after LaTeX finished typesetting the text. The package does this after every paragraph (this having something to do with LaTeX's internal workflow). However, when a paragraph is punctuated by equations, the portions before each equation environment is processed before the equation is processed. So when the package tries to number the lines for one of such paragraphs, it only knows about the last block of text not interrupted by an equation environment before the paragraph break.
To deal with this the package defines a wrapper to be put around the math environments so that it flushes the numbering before entering the math environment, numbers the equation when leaving the environment, and resumes as usual afterwards. So the work around described in the manual is to enclose the equation environments in this wrapper.
Now, to make life slightly simpler, you can also pass an option to lineno to automatically redefine the math environments to include the wrapper. But this will likely not work with document classes that defines their own math environments (such as AMS-LaTeX's align).
Figured it out - one should use the \internallinenumbers directive, like this:
\begin{figure}
\begin{alltt}
{\footnotesize{\internallinenumbers
def insert(k, v)
// ...
}}
\end{alltt}
\end{figure}
Best Answer
I will be happy to delete this. In the manual in section 4.7 How the line numbers look like you find the example
Obviously you may replace
\normalfont\bfseries\smallby whatever you like, and as e.g. discussed here also change the color and so on.