Which PCB software is best on Linux platform, for medium size designs?
Both open source and commercial?

AFAIK mentor and cadence products are work in Linux
try this:
mentor expedition enterprise
http://www.mentor.com/products/pcb-system-...ion-enterprise/

Cadence allegro
http://www.cadence.com/products/pcb/pcb_de...es/default.aspx

Also try to look here :
http://alternativeto.net/SearchResult.aspx...;search=tag:pcb


And Here :
http://www.designspark.com/pcb
http://www.opencollector.org/summary.php#PCB
http://sourceforge.net/projects/geda
http://sourceforge.net/projects/mkpcb
http://sourceforge.net/projects/reds
http://sourceforge.net/projects/circuitsmith
http://sourceforge.net/projects/tinycad
http://sourceforge.net/projects/glpcb
http://sourceforge.net/projects/gpcb
http://sourceforge.net/projects/layout
http://sourceforge.net/projects/pcb

KiCad - open source

CadSoft Eagle

Thank you for extensive answers.
I have seen Allegro "in action" and it seems that it's too complex, i.e. it takes a lot of work to setup a design, or I don't know how to do it efficiently.
Is it the same for Mentor Expedition? Or is it easier to setup and use?