Anyone knows what "Relayed Skype-2-Skype call quality improvements" means exactly? In what ways the call quality was improved?

Call quality was improved in those situation when skype cannot establish direct connection between the call participants thus making the connection through another user, so the call becomes relayed.
Regards,

Thanks for the reply.

I typically get 4 relays with other parties. Both have routers. Does a router count as a relay (in other words do we establish a direct connection)?

Regards

No relays are other pcs that have skype running, so in your case the voice goes through 4 other machines before it reaches you friend, encrypted of course.
Regards,

To get the best quality you realy need zero relays if possible.

Thanks. Unfortunately, I guess I have little control over the number of relays ...