I generally don't regret my lack of a formal CS degree. My EE background generally seems to have adequately prepared me to write software, as most of what you need to know, you don't learn in CS classes. Still, I do occasionally think about how it would be interesting to go back and take some classes, to learn some of the more formal stuff, like algorithms and data structures. Usually that's when I just go pick up a book on the topic and read it, to much the same effect.
Sometimes you don't have to buy a book, though. Today I was reading this series (particularly, the latest entry), and I really liked it. Choosing an appropriate data structure is an extremely common task in programming, and it's not always simple. For example, in just the last six months, I've had to deal particularly with how to represent directed graphs efficiently, and having read this beforehand would have been helpful.