It looks like the much awaited Content by Search Web Part might start showing up in Office 365 tenants! I’m not sure when this started, and it might not be on all tenancies just yet.
Here it is in all its search laden glory …
It seems to depend on what version your Office 365 tenant is. If you have 18.104.22.1680 or above then you should be in luck.
To find out what version your tenancy is on log in and navigate to the following URL:
You should see something like this:
Update: MS has announced this now: http://blogs.office.com/b/office365tech/archive/2013/10/29/search-innovations-for-site-and-portal-design-in-sharepoint-online.aspx