First, thanks for the support! Especially what you said Yooper.
I believe I am well on the road to solving this problem, so hopefully other people who Google "foamy soda" and just get more confused like I did will benefit from this post.
For some reason, the soda seems to be overcarbed or something.
That made me realize that my soda is over carbonated. That certainly explains the high flow rates. But my pressure was at 38 PSI, could 3 PSI really make a difference?
Well, it turns out that my kegerator was running colder on average than I thought. So with the soda at 38PSI and 36.5F, it was getting way too carbonated.
I turned the pressure down to 25PSI and things seem to be much better. It still needs a little more carbonation in the soda, but I'll let it sit a few days to see if it gets it.
So when you're thinking about over carbonation remember that the temperature of your brew matters too!