A bristlenose will stay smallish. You have plenty of space in that tank for cool stuff if you wanted it. When I had eels years ago i kept them in very small grain pea gravel and they loved it. I would see heads poking out when they thought no one was looking. I had a yellow spiny kind though and not the bigger ones. You will need driftwood for the the plecos as they require to have some to munch on, although I have never noticed the wood deteriorate from this. The bristlenoses in my African cichlid tank certainly seemed happier when I got a small piece and hid it in the back.
There are some beautiful South American cichlids out there besides the fish you find at Petsmart, and maybe a few that are at PS. Amoung the more common ones you find there, Angels while ok as young, really come into their own as adults with very bold colors and size. They are also sedate and peaceful enough to not spook the eels. I would avoid oscars like the plague if i were you. They really dont have anything going for them, and if I had a fish to call above all others a trash fish, it would be an oscar.
As to why the PS people gave you bad info, they really arent trained. I used to work there back in college and there is no training program. They have no say on what goes in what tanks as well because corp comes in and tells the stores what goes where and god forbid they do a pop inspection and a fish is out of place regardless of whether its better for the fish or not because corporate "knows" better. They are basically told to tell you, "these are community fish and go well together, these are semi-aggressive and go well together, these are mean cichlids and they fight each other"(lol I am actually picturing one of my old co-workers saying that in a chippery voice.) Occassionally you will run into someone who actually knows what they are doing but you have to get that out of them because they are jaded from answering one hundred times a day "why did my fish die? I want 20 more neons to replace them with." I was a bad employee, I knew African cichlids well, not so much on the South American, and knew normal joe fish well, but I quickly got tired of telling people why their fish died and then they would go ask another employee the same question to get an answer they liked and get them to give them twenty more fish for their "big" 10 gallon. I'll get off my soapbox now.
You can always order fish online, some places have some pretty good deals. I havent checked but i imagine the sponsors of this website can help you with some good fish not found at PS and they will probably arrive healthier with as good a garauntee(sp).