Google has three products in this field: Maps Engine Lite, Maps Engine Pro, and just plain Maps Engine. This page explains the differences, but it sounds like you would be best off with Maps Engine Pro.
- Both Lite and Pro let you embed your map easily into another webpage. No programming, OAuth etc needed, just copy and paste the pregenerated code.
- Pro lets you add up to 2,000 points per layer onto a map, with full custom styling. (Lite is limited to 100 per layer and a set of default icons.)
- Lite is free, but Pro costs only US$5/month, so it's not going to break the bank.
The only issue is going to be that search box. Maps Engine Lite & Pro maps in the default standalone viewer have a search box that does what you want, but the embedded iframe version only has a list of points. Might be good enough if you don't have too many?