Issues with the entity field output
If I may, you're not doing this in the most optimal way.

The best solution would be to implement hook_views_data(), and describe your custom entity's base table to Views. Then you can use Views to build your page through the UI, and all of your entity's properties and fields will be available to output as fields, filter by (exposed or not), and sort by. 

You get all of the flexibility you're used to with Views for nodes, and it's easy to write custom field/filter/sort handlers for your custom properties if they need a bit more functionality than the default.

To answer your original questions (in case you don't want to go down the Views path):


Remove the required attribute after the call to field_attach_form(), e.g. unset($form['field_foo'][LANGUAGE_NONE]['value']['#required']);
The order isn't broken, it's exactly what you've asked for. If you want the fields to appear before the search, but field_attach_form() before the definition of $form['search'].