If you can succesfully implement a graduated colors renderer then you are almost there. In the IClassBreaksRenderer there is a property for Symbol. Just pass a symbol (which contains the size) into this property for each break index.
Glad you got it working. That ILegendInfo class can be confusing because it controls the appearance of layers in the TOC and their renderer in the symbology tab. Don't forget to mark this thread as answered.