My first controller rspec test
It looks really good to me. All I have a very minor quibbles/suggestions.

Since you're using FactoryGirl, you should be able to use create_list :user, 4 instead of the 4.times.map { ... } block

You might as well check that a new record be_kind_of User. Just checking if it's an ActiveRecord is a little loose.

You don't need to create many users for some of these tests (like #show and #destroy). It's fine to do so of course, but the more tests you accumulate the faster you'll want your tests to be. And fully creating several records may be a bottleneck, especially for something like user models that likely have a uniqueness validation. That'll cause Rails to perform extra queries (one to check if the record is unique, and another to insert it in the DB).

Lastly, try running rspec with the --format documentation option, if you're not already. It'll format the output like so

UsersController
    #index
        assigns all users to @users
        success
    #show
        ...


which I personally prefer because it reads well (and, as the name implies, documents stuff). But for that same reason, you may want to change success to succeeds and when valid to something like with valid params just so you get nicer sentences.

Again, this is all really minor stuff.