Required delta between proceedings and journal versions I am recently getting my papers rejected from journals (i.e., TALG) on the mere basis of not having a significant difference between the journal and proceedings (i.e., SODA) version.

The main reasons for me to submit to a journal is its thorough review process.
Other than that, SODA's 20 page limit is more than enough for all that I want to say. In fact, David Johnson has repeatedly asked the SODA crowd to not "save stuff for the journal version".

Any advice?
It depends. If you write a paper and exhaustively include all of the relevant materials, then you should submit the paper to a journal (if you think the journal you choose is more valuable then a conference on the basis of impact factor, reputation and other metrics). If you only describe part of the work, then it may be better to submit to a conference and later, when you have new/updated results, then you may consider submitting again to a journal. What constitutes a significant difference is of course highly variable and depends on your particular work. A very rough rule of thumb is that journal versions differ for at least 30% from corresponding conference versions. However, there are exceptions. And, finally, you should carefully decide the venue. Especially in TCS, a conference may be extremely valuable, in some cases even more than a journal. I do not think that the review process applied in some highly valued conference is worse than the average review process applied in journals. This is strictly dependent on the particular conference or journal, and on the reviewers an editor finds available.