I have a cyanogenmod phone without google for 6 months : I use F-droid as a market. The main advantage is that you can add other repository. Thus I have the classical F-droid one plus the guardianproject one but you may add others one.
For my "evryday wihout google" life I use :
K-9 mail (+APG) for my mails (Apache2)
Gibberbot for XMPP conversation (it deals OTR and can even be used in google talks ) (Apache2)
Firefox as webbrowser (MPL2)
duckduck go apps as search engine (Apache2)
The Diaspora webclient (GPLv3)
Jamendo to listen music (Apache2)
KeePassDroid to manage my password (GPLv2)
Offline Calendar as a calendar without synchro (he is efficient but ugly :/) (MIT)
OsmAnd as maps and GPS stuff (GPLv3)
Yaaic as an irc Client (GPLv3+)
I don't have problems when browsing except on youtube.... :P