A lot of people have been complaining about this.
My experience (playing at all levels) has been that they are FAR more likely to offer a good deal if you have competitive culture, military, and tech behind you. I get bad deals when I'm in a low-culture mode (and my advisor says they aren't impressed by my culture - guess this is why he brings it up).
My first few games I was stuck in limited terrain and wound up with few cities, but they were large and incredibly culture rich. I got great deals from the AI. I would trade them maps even or get money in addition to maps, ditto on the techs. I would regularly get two techs for one (slightly higher) tech.
My most recent game turned into an ICS strategy and among my 20 cities I get about 8 total culture per turn. Result: lousy trade offers until I thump them with my immortals
I don't know if others have noticed but it also SEEMS (I have not yet enough data) that it makes a difference where you make contact. I have taken the habit of trying to contact a unit near my most cultural city.
Fun bargaining trick: the computer values cities very highly. Take a settler you don't care about into their territory, maybe dump in some captured workers if they are spare, and you can sell it to the opponent for great return! If you do it at the border near a cultural city you might even get it back soon
