I will preface this with "I haven't done this" so this is just an
idea...

You can add a hidden content editor web part on the page where the web
part appears and add CSS code that overrides existing web part styles or
add new CSS code that styles the web part based on nested HTML tags in
the rendered display. Otherwise you can probably only control the
background color  if it is a custom web part.

Any thoughts on second part of the post

- Creating border  of a webpart. Although this property  is listed
in "Frame Style" of webparts  as "Title Bar and Border" but have never
seen it doing anything different than "Title Bar Only".

Here is a solution which I found that worked in cases of webpart  that
are available with the creation of lists and document libraries.

By default sharepoint provides default views for lists and libraries.

Review the following article

msdn.microsoft.com/.../en-
us/odc_SP2003_ta/html/ODC_WSSAddingCustomViewStyle.asp

There is a style

.ms-alternating {
background-color: #99CCCC;
}

which is used by "Shaded" style  in the lists and doc libraries.

One can create a custom view style which is copy of Shaded style
provided by default, tweak it so that instead of alternating rows
getting shaded, all rows are shaded.

Create a new view for a list, select the new style, and apply that
view in the webpart that you are interfacing in the webpart page.

No, that is why I didn't add anything. I have experienced the same
thing.

My only thought is that the SharePoint CSS styles don't provide for a
border color  or override it at some point. But I haven't investigated
it.

I thought that there was a CSS class for Web Part border. I just don't
remember what it is and I don't have a SharePoint environment to check
right now.

The OWS.CSS file in the Styles directory can be
modified to change  this...

On our installation, the border-width was defaulted to
0...thus it never changed when modified from the users
toolpane.

.ms-WPBorder
{
border-color: #afc9ef;
border-width: 1px; //change made here
border-style: solid;
border-top-width: 0px;
}

Great, however, don't modify the OWS.CSS file. Get my custom site
definition at our Premium Content site:
www.mindsharp.com/default.aspx?premium=default

You can read my Site Definition customization article published in
SharePoint Advisor magazine here:
http://zones.advisor.com/doc/16799

It will show you how to create your own custom OWS.CSS providing Site
Definition level overrides to the Microsoft owned OWS.CSS file in the
style directory. Protect your future.