find . -name "prefix*.c" -exec sed -e '/pattern1/G;a\{new line1' -e'}' {} \;
I got the "G" part from examples and never did verify its offical capabilities, but that's what adds an extra blank line (from man, it seems to be appending the swap line to the current line?). The two -e arguments are the key to overcoming the difficulties with the "a" command.
In the spots where I wanted to add the line before a particular line, I didn't have time to figure out how to make a single command that would add the extra line plus a blank line, so I just wimped out and used two commands. The "x;p;x" bit is from another example in the single-liner file:
find . -name "prefix*.c" -exec sed -e '/pattern2/i\{new line2' -e'}' {} \;
find . -name "prefix*.c" -exec sed -e '/pattern2/{x;p;x;}' {} \;