I'm linking this older post b/c it has some good resources:
http://www.dcurbanmom.com/jforum/posts/list/505938.page#7725066
Remember that flower beds are going to be more work than shrubs. So start small.
This is a great resource for native plants:
https://www.nps.gov/plants/pubs/chesapeake/
There's a handy guide to plants that attract butterflies and that means flowers (as well as host plants). So as to make it easier on you, I'd start with flowering shrubs, then add add flower beds around them.