Note to self:

Next time you need to add a Processing Instruction (PI) to an XmlDocument, ignore the MSDN documentation sample which uses XmlDocument.AppendChild.  That sample isn't exactly incorrect, however it does result in the PI being appended to the end of the document , which probably matches about 0.0001% of the typical usage scenarios. 

Using XmlDocument.InsertBefore( PI, XmlDocument.DocumentElement) is what you were looking for.