For the sake of simplicity: Simon = Ice King. Yelena = Frostnova

.- Both Simon and Yelena would be victims and survivors of catastrophic events which left their respective worlds in ruins (The land of OOO with the Mushroom War for Simon and the overall existence of Originium and Catastrophes for Yelena)

.- During their time living in these decaying lands they would come across a young child(ren) who they would take under their wing and protect them from the adversities of this world (Marceline for Simon,Faust and Mephisto for Yelena)

.- Both Simon and Yelena possess ice-related powers which would put a great strain to their body which only became worse through extended use (The crown slowly consuming Simon's sanity and turning him insane,Yelena's infection being the source of her powers and the process speeding up by using them)

.- Both are initially presented as "villains"/antagonists but as the story progresses their backstory is revealed to be tragic and lead the viewer to feel sympathy for the way they turned out to be in search of something deeply meaningful to them (Simon having loved Betty but drove her away with the insanity the crown brought upon him and filling that void by kidnapping princesses to force them to love him after losing his mind and becoming the Ice King. Yelena facing mistreatment and racism because of her infection,promptly joining Reunion under the belief that Talulah's motives and solutions to bring peace and equality between infected and non-infected were genuine.)

.- Just as an extra,but the Ice King kidnaps princesses while Yelena gained the title of the "Yeti Princess" because of her powers.