Maybe smoked salmon with capers, red onion and cream cheese. Or a butternut-squash soup with bacon garnish, and a mixed green salad with toasted pecans and goats cheese.

Berries and whipped cream, a cheese plate, since you do dairy.

I've always found bacon and black coffee to be sufficiently "girly." Not to be snarky. :) How about smoked fish/kippers/herring/mackerel/sardines?

I would go with sliced banana with Paleo Nutella swirled on top. Garnished with dried rose petals or cinnamon.

I love the egg muffins idea, plus someone else's idea about whipped cream and berries, but perhaps a baked almond flour based item like madelines or financiers? Those are both very girly, delicate treats. You could always do a regular financier recipe, and use a tiny bit of all purpose gluten free flour as the flour (the ratio of flour to almond flour is already small in financier recipes) so it should still taste good, even white rice flour could suffice. Good luck and have fun!!

How about a Moroccan style orange salad? Get gorgeous oranges. Peel by slicing the skin off with a knife. Slice remaining orange horizontally. Lay out on a pretty platter and spritz (if you can) with orange blossom water. Or brush a little bit on, or ever so gently toss or sprinkle. Shortly before you serve, sprinkle the orange slices with some nice cinnamon. It's one of those things that is greater than the sum of its parts.

Here is what I would serve

Pickled plate - Blue Cheese stuffed olives, fresh thick-cut pickles, pickled peppers and cauliflower.

Caprese Salad (Whole milk mozzarella, fresh basil, fresh tomato, olive oil, balsamic, salt and pepper).

Smoked salmon wrapped around cream cheese, bacon, and a green onion.

Egg salad with bacon, rolled into lettuce leaves or served on ribs of celery, topped with chives.

Dessert: Slightly frozen strawberry/banana puree with shaved dark chocolate served in a martini glass.

I made an awesome goat cheese & mushroom tart for my husband for Valentines day: http://freshhabits.blogspot.com/2012/02/mushroom-goat-cheese-tart.html You could also use the same idea to make mini-tarts in tartlette shells. Or a similar quiche like filling in individual custard cups.

I'd totally do the berries & whipped cream thing too. And perhaps proscuitto wrapped melon slices. And lox rolled around cucumber & avocado and sliced into sushi rolls garnished with capers. And either deviled egss or a few heart molded eggs, like here: http://www.annathered.com/2010/09/29/how-to-make-a-heart-shaped-egg/

Yeah, brunch ideas, I haz them.

Grilled asparagus as a base, with salmon in the middle, and a poached egg on top. Served with fruit salad and sparkling water with a few frozen berries as ice cubes.

Dark chocolate covered strawberries?

Reuben Benedict (is that girly?) http://cavegirlcuisine.net/2012/07/07/reuben-benedict/

Or these crab/salmon cakes as a base for Eggs Benedict instead of muffin: http://ourlifeinfood.com/2012/09/02/salmon-and-crab-cakes-with-avocado/

Pear Pancetta Crisps with Goat Cheese and Honey Drizzle for brunch dessert or app (I like it better with fig honey than real honey) http://www.eat-drink-smile.com/2010/11/pear-pancetta-crisps-with-goat-cheese-and-honey.html

Cobb Salad Deviled Eggs (yogurt is optional) http://appetizer.betterrecipes.com/cobb-salad-style-deviled-eggs.html

And I will always love mimosas with brunch. Paleo or not, I adore the $10 bottomless mimosa weekend brunches they have around here.

Be trendy. Serve up some meat in those cute cabbage leaf cups.

frittata, a beautiful fruit salad, a nice green salad, and some home roasted nuts?

There are certain flower petals you can eat. Since they are non-paleo you wouldn't hurt their feelings with some half dollar sized coconut flower pancakes and maple syrup.

not sure if your in the UK or US but in the UK we have a sort of small tea room chain called boston tea party - absolute beaut of a place!! anyways me and the girls used to go their for girlie breakfasts before i went all paleo - still go their once in a blue moon for a "treat" and suffer for it later mind!! i adapted my favourite menu choice - pancakes with greek yoghurt and seasonal fruit compote - just do the pancakes paleo style =) and make sure they are served piping hot - makes them more delicious espesically with hot coffee =) enjoy!! p.s also try with a side of bacon !

M