You might like to know about Context Free Phrase Structure Grammar (CFPSG), which is similar to the approach you're taking, but it allows for intermediate categories, like NP. I'll give an example reformulation for your example:
S -> NP VP
NP -> D N
VP -> V AJ P CNP
D -> an
N -> apple
V -> is
AJ -> red
P -> in
CNP -> color
If there is a way to derive a phrase by starting with S and using rules to make substitutions, then the phrase is said to be generated by the grammar. A set of phrases all of which are generated by such a grammar is said to be a language generated by the grammar.
An advantage of having such intermediate categories as NP available, is that once you have described the fact that "apple" is not a good NP in subject position, it will follow that it is also not good in other sentence positions. *"I'd like apple".
CFPSGs have had much use in grammar and in computer science. The classic Unix tool yacc, "Yet Another Compiler Compiler", is based on CFPSG, for instance, and the languages generated by CFPSGs are those recognized by the push down store automata.
The answer to your first question is that neither sentence is 'more grammatically correct' than the other. Nor is there any difference in meaning.
The difference between the sentences is in the frequency of the respective constructions. The first sentence contains forward reference from the pronoun he to its antecedent Oedipus. The term for this forward reference is cataphora (also known as anticpatory anaphora).
Conversely, the second sentence contains backward reference from the pronoun to its antecedent. This is anaphora, also known as retrospective anaphora. Anaphoric reference is much more common than cataphoric reference.
Quirk et al. in A Comprehensive Grammar of the English Language (p351) state:
Cataphoric reference occurs much less frequently, and under limited
conditions.
As to the second question about general rules for phrasing such sentences (e.g. the limited conditions), the CGEL notes:
It (cataphoric reference) generally occurs only where the pronoun is
at a lower level of structure than its antecedent.
Dependent or subordinate clauses are an example of what the CGEL means by 'lower level of structure'. This is the case in the present example, where the dependent clause contains the referent pronoun he, and is followed by the main clause with its antecedent Oedipus. It is not permissible, therefore, to use a cataphoric reference if the two clauses are reversed:
?He blinded himself as punishment, when Oedipus learned of the sins he
had committed.
As the CGEL points out, he and Oedipus "must be understood to refer to two different people."
The difference between the two constructions, therefore, is a stylistic one. The CGEL states:
On the whole, cataphoric reference ... is associated with formal
written English.
The Wikipedia article on Cataphora claims:
Cataphora across sentences is often used for rhetorical effect. It can
build suspense and provide a description.
There is a good article on Cataphora at About.com with many examples from literature and the media.
Best Answer
The only existing answer is at best misleading.
Note that the only "non-standard" variant above is easily recast to full acceptability:
There's no difference in meaning whether the negation is applied to the verb (give/do not give, hurts/doesn't hurt) or to the object (anything/nothing, anyone/nobody).