Sofa to complement two Paulin Little Tulip chairs?  

Arne Jacobsen Swan sofa maybe?
http://www.designaddict.com/atlas/Arne-Jacobsen/Swan-Sofa-model-3321

I like the style of Swan Sofa, but, at 56" wide, it's more of a loveseat than a sofa.
 
Also, like a lot of the Fritz Hansen stuff, it seems to be expensive even compared to other designer furniture.

those Eames sofas look like the back seats in my dads minivan

The Eames doesn't go.  Keep it European, Harcourt Cleopatra-
http://www.designaddict.com/atlas/Geoffrey-D-Harcourt/Cleopatra-Sofa

The Cleopatra lounge is cool--but it's not really a sofa, is it?  I really want something I could sit three people on, but I also want something that isn't ginormous.
 
What about an Ondo sofa (also from Artifort)?

No, do not fight a War of the Legs.
You should probably have some sort of a personal, at least quasi-professional style/needs consultation with somebody if you're seriously considering purchasing this stuff.
 
That Kit Kat Korporate display looks terrible!

I'm into either getting totally matching pieces or completely opposite pieces for total contrast. In between matching, which is what you're doing, to me is sort of like you were trying to find a matching sofa for your chairs but you couldn't afford it or you didn't look hard enough so you had to settle for something that was similar but not matching. I think a boxy sofa would create nice contrast with these Paulin chairs!
 

^copy that, partially-
The basic elements should be varied so as to evade monotony
"related products" ---->  http://hivemodern.com/pages/product197/artifort-rene-holten-mare-2-seate...   ----> This would work nicely with the pedestal base chair.  
(stupid internet world...)
also... I guess while a personal consultation with a knowledgeable professional may be theoretically desirable, interior designers tend to be idiots, in my experience... (I sure wouldn't trust one to select my furniture).  Dialog helps to resolve questions, though, even if it's just with yourself.  
 
 
(mutters incoherently, moves erratically away with a shuffling gait and furtive side-to-side glancing)
 

if you're wedded to something rounded, you might think about the noguchi sofa, seen here:  http://shop.noguchi.org/nogfreefsofa.html
and at the risk of echoing those above, I also like mixing different styles.  somehow I think it would make the paulin chairs POP--!
best design advice I ever received was to buy what I really loved, regardless of shape/era/provenance--the idea is that one's individual 'style' would emerge. 

I would go with contrasting forms, too.  Heck, I HAVE gone with contrasting forms in my own home.  I love the look of it.

Yup, same here.  Too many exposed furniture legs in a room (except when placed upon a very deep pile shag rug...) can look messy.  
Best,
Aunt Mark
 
ps I am having a hard time wrapping my arms around the way that the designer has placed those Nelson Swag tables with the Eames Surfboard table in the above snappy.  Remove them at once!!!

Hi all!
 
I now know what the situation is with the "nested" tables (as shown above).  Rumer has it that the housekeeper needed to mop up cocktail residue from the floor (below the swags), and forgot to place them back into proper positionment.  Also, since the owner is out of town, the cleaning crew brought over a few terrariums, as shown.  I blame Ray.   
Best,
Aunt Mark

To whomever suggested the Noguchi sofa:
 
It's nice, but it appears to be the size of a battleship.

Before you jump, think about the coffee table you're going to choose.A room can look a bit odd when ALL the furniture is up on legs. I would choose at least one piece that is "grounded".
If your space is very small, I would make the largest piece-probably your sofa-the leg piece that you can see the floor all the way through on.