I have a question about TCS journals. As I am trying to follow your advice on being more diligent about journalizing my papers, I realized that I am surprisingly ignorant about where to send them. A couple of more senior colleagues I asked didn't really have the answers.
What are the journals that accept theory papers? What's their specialization (if any)? What's their relative quality/reputation? What's the expected turn around time for each of them? Anything else I should be asking?Sounds like a list that should be on a site we can edit in the future like Wikipedia and in fact they have such a list. It can use some additions, links, publishers and specializations if anyone is so inclined to help update it. Most of these journals cover general theory unless their title indicates otherwise.
For reputation I put JACM first, followed by SICOMP, followed by a rough equivalence class of the most of the others. Information Processing Letters has only short papers, good for a result that has a simple proof but still worth writing up.
Turn around time depends more on the editors and the referees than the particular journal. The average time from submission to publication (assuming no major issues found in the referee process) is a bit over a year with a very large variance. Feel free to ask/bug the editor if you need faster publication.
Another big issue to consider is which publisher to choose. It can affect who can access your paper, where it will be indexed and archived and how and whether the paper will appear in print and/or on the web. I'm a (biased) fan of the ACM with its well-organized low-cost digital library but there is something to be said for open-access journals.