I've never had a problem with the Waltz and Ice Lion. I usually just steal the Waltz's two items (Silk Shirt and Remedy), and then kill him off—if you kill the Ice Lion first, the Waltz will just resummon it—then steal from the Ice Lion (Mythril Dagger and Ether) and kill it off. Heal with potions and hi-potions when necessary.